800
-9865659 -8898614 -8738750 -8680326 -8448319 -7681858 -7624678 -6504594 -6104127 -6112078 -5195347 -5226837 -4301295 -3723879 -3666107 -2749213 -2767590 -2122959 -1252425 -1058973 -22302178 -21886689 -20969976 -20854333 -20357301 -19873324 -18997375 -18072138 -17719870 -17389348 -16751738 -16651856 -16390685 -15442947 -14334813 -13534058 -13025076 -12126003 -11317082 -10879685 -30899797 -30172164 -29637581 -29477236 -29130957 -28563797 -28121497 -27438121 -26333544 -26425171 -25605757 -25539421 -25204929 -25072131 -24833879 -24863847 -24107272 -23009902 -22987337 -22982195 -39638490 -38799743 -38275030 -37814590 -36772470 -36097126 -35396986 -34556527 -34556519 -34310976 -33979310 -34058746 -33405412 -32836572 -32213227 -32210593 -32015929 -31649552 -31490959 -31205387 -51783122 -51297854 -51364828 -50962287 -50255998 -50020473 -49285429 -48807737 -47816947 -46760813 -45906040 -45348747 -44825590 -44789273 -43727629 -42647797 -42678991 -42066717 -40945901 -40609865 -58846523 -58348156 -58432563 -58466998 -58345743 -57352883 -57374939 -57142933 -56684054 -56543728 -55898445 -55225807 -55236993 -55083374 -54437469 -53558159 -53282146 -53338855 -52589838 -52347011 -67812771 -67148544 -66803902 -66133585 -65334371 -65339736 -65127035 -65014637 -64783157 -63977641 -63318553 -63282236 -62373652 -61660118 -61309009 -60359057 -60323983 -60246184 -60297768 -59177899 -78551220 -77921920 -77895486 -76959981 -76459345 -75693083 -74806243 -73764104 -73715344 -73776258 -73049279 -72863328 -72108971 -71078632 -70275164 -70121704 -70059644 -69739071 -68792613 -68642228 -84749658 -84872594 -84613236 -84529941 -84220048 -84214334 -83668593 -83765632 -83733854 -83355678 -82922590 -82704629 -82008376 -81048240 -80958659 -79939012 -79466167 -79502229 -79248425 -78815071 -94854657 -93891247 -93736500 -93019288 -92354153 -91610964 -90980368 -89902860 -89417905 -89322330 -88906046 -88593295 -87955133 -87786588 -86697552 -86560458 -86672717 -86069923 -85806633 -85311227 -105224033 -104617383 -103951705 -102926300 -102306733 -102040906 -102123067 -101404321 -100525160 -99420639 -99095107 -98918619 -98511471 -97547627 -96606237 -96231744 -95962129 -95403111 -94907515 -94836777 -111222206 -110973964 -110862096 -110937817 -110755808 -110878431 -109834971 -109437555 -109225954 -109292072 -108799778 -108301179 -108090381 -108031545 -108060304 -108180165 -107896797 -106857622 -106055298 -106167447 -121754514 -121659921 -121404326 -120309495 -119726821 -119680417 -119102873 -118445190 -117758047 -117039936 -117043459 -116088801 -115507331 -115112411 -114817819 -114707752 -113879914 -112870435 -112442683 -111512830 -130860123 -129823344 -129431538 -128865369 -128765528 -128173382 -128122006 -127367511 -127314327 -126948185 -126740994 -126422884 -125355972 -124509167 -124256790 -123687995 -123696901 -123063639 -122206826 -122089996 -138639682 -137632508 -137563457 -137007318 -136520414 -136188159 -136243917 -135773818 -135350711 -134737644 -134842274 -134900754 -134346392 -133893466 -133185648 -133047096 -132418388 -132039234 -131564553 -130971445 -149975399 -149407426 -148860250 -148315040 -147263089 -146772368 -145778191 -145459293 -144815018 -144584575 -143962550 -143482474 -143133834 -142242528 -141771930 -140993115 -140802077 -140655127 -139679192 -139494102 -161150347 -160315227 -159650146 -158729271 -157872766 -157040066 -156840942 -156438028 -156339911 -155265011 -155307112 -154372144 -153316392 -153075242 -152940182 -152411266 -151784761 -151879496 -150910770 -150670613 -172184104 -171850207 -171061101 -170797194 -170528079 -170294922 -169570171 -168537763 -167709476 -166641114 -166165847 -165252845 -164892823 -164280650 -163662403 -163310949 -162963420 -161980084 -162047811 -161390439 -183658502 -182677823 -182331909 -182096799 -181769891 -181482145 -180859723 -180890482 -180607868 -180309082 -179617362 -179117693 -178664892 -177977182 -176897768 -175790696 -175306213 -174709270 -173698527 -172996556 -191568408 -190665306 -190325925 -189853850 -189700908 -188700406 -187659478 -187463148 -187080958 -186851709 -186078831 -185531617 -185579462 -185356944 -185111307 -184998891 -184918222 -184936211 -185018359 -184095345 0 995237 1448560 1918709 2635494 2732210 3685077 4119614 4179366 4573649 5316269 6268023 6639956 7745553 8528976 8626737 9678074 10112595 10417656 11067312 11585283 12334539 13406610 14058233 14662768 15148132 15240690 15136985 15074276 15804858 16917773 17486334 18372105 19264880 19536190 20364140 20624329 21077848 21090050 21582746 22624390 23155950 23242781 24111140 24548981 25082400 25434085 25716633 26250141 26477086 26841397 27710605 28804011 29170461 29862041 30798613 30791406 31117702 32089813 32809135 33545660 34560759 35435726 35925512 36200476 36492466 36857585 37911270 37813516 37733916 38806058 39193390 39578843 40272605 40315451 41218779 42015932 42631987 43619212 43938687 43867227 44037473 44278343 45200444 46116450 46947963 48053706 48475929 48752241 48863705 49164022 50159584 50622956 51539690 52070675 52158771 53051838 54128639 54439787 54854051 55359568 56174605 56211628 56781577 57675972 58730189 58717224 59061999 59308062 59222925 60251830 61123861 62051094 63152110 63201840 63759263 64284650 64496903 65505845 66448020 66744345 67093183 67896103 68528030 68732486 68635315 68819579 69938413 71059515 70966005 71465947 71407556 71780260 71774859 71653032 72495931 73510833 74014318 75017651 75176158 75795383 76871804 77555618 77973979 78786542 79084965 79089712 79540134 80139074 80405839 80850522 81213877 81997747 82196019 83101667 83076517 83752710 84722879 85468147 86041765 86245476 87317780 87825682 88789240 89206968 89371575 89686911 90193349 90322738 90410672 90300523 90202199 90080647 90775119 91500399 91819470 92601568 92773572 93613348 94220494 94667145 95644484 95737528 96245069 97049441 97343065 97677694 98792519 99855646 100968320 101553884 102649643 102591847 102543050 103618252 104188221 105027402 106111133 106949757 107015540 106917446 107687682 107832305 107945146 108323647 109021622 109987982 110836849 111488879 111382764 112019423 111985370 112316113 112273447 112862962 113866510 114494726 114399922 114486666 114833527 114771361 115275545 115313803 115484164 116229355 117234269 117478865 117567609 118374592 118963604 119145561 120125789 120405809 121156616 121295319 122197291 122389505 123478773 123427745 123940388 124217451 124644062 124596753 124747274 124671017 125544135 126145845 126561972 126705356 127161610 128195681 128114832 128421418 129324021 129739098 130831402 131839401 132292408 132917530 133863367 134093429 134176648 134170623 134582557 134669376 134916303 135561660 135881560 136305917 137241770 137162471 137740807 138628788 138571674 139696634 139777838 140568339 141084150 141263109 141592549 142271386 143272966 143899833 144144518 144748765 145202952 146259037 146789937 147862676 148751021 149733914 150722232 150764427 151128921 151399343 151601940 152100803 153151159 154233551 154612288 155102272 155387380 156251823 156415146 156768554 156739600 156944234 156863494 157801422 157951507 158000671 158867548 159108908 159941268 160488768 160606792 160490697 160388113 161061858 161434231 162037436 162311803 163323585 164045054 164900802 165361976 165555130 166424835 166995099 167336097 167914624 167964163 168701900 169037940 169098427 169792621 169807581 170070001 171132450 171422179 171834906 172908670 173215429 174136605 174500340 174673556 175365942 175680070 176054894 176342224 176898043 177263854 177660337 178561828 178745071 178651143 179065049 179820837 180323056 181267722 181712663 182713980 182844688 183887745 184739647 185738983 186329718 186655421 186660858 187585720 188564349 189485040 189870116 190896211 190897777 191139329 191699036 192759058 192706583 193577373 193497065 193799698 194195236 194625506 195156465 195803205 196664835 197048788 197818225 198246719 198671232 198590393 198601849 198944586 199298128 199298957 199684206 200071668 200129448 201029504
597830444
10000
716 253355967
126 10251111
447 272311899
598 213052247
333 46690406
45 221355656
671 130046935
780 149396632
349 697901040
411 63425679
79 1000000000
578 285825511
701 1000000000
649 225208021
47 309094470
535 117837651
140 986720888
54 90137300
797 627711884
460 787578858
330 8674180
738 253671768
699 625791388
287 352946143
247 829900245
557 24212425
392 92382204
786 8075221
276 206055683
535 229364466
132 300842212
164 1000000000
224 182308817
129 32049423
16 294777983
21 639613954
795 42958407
522 28423512
74 1000000000
646 358690112
421 53140197
434 513064018
84 30483515
22 1000000000
127 22685728
153 27951428
558 142198937
549 94831903
488 70516439
576 1000000000
342 66582526
83 1000000000
672 134551559
38 401936111
654 3866428
1 466973056
583 17960026
427 1000000000
533 257166267
750 1000000000
638 8434563
368 151072951
555 36993147
474 257225392
228 38660149
243 1000000000
49 886126903
421 15503674
89 31954165
534 26443018
645 323357656
495 524326236
157 61542886
472 265741291
297 731399802
633 147426750
369 1000000000
506 1000000000
157 1000000000
290 310791921
244 40819486
155 27066484
735 329483483
523 1000000000
102 1000000000
731 66102789
81 310761599
178 31157009
519 6161242
122 57032986
626 10587858
665 56512108
568 196492436
632 44538444
706 505594113
191 97193666
344 751274403
534 106236069
578 1000000000
292 21053660
199 139596900
723 222469629
112 784508468
41 96703059
581 7023870
239 124827529
142 3797751
333 20238783
627 356935836
458 504840218
60 329687
368 16393007
496 244220267
389 93871205
728 171766142
722 10867439
60 75628274
639 214379081
580 1000000000
20 46349580
535 451385745
664 381211380
671 1000000000
341 80337758
162 19213400
529 310070825
745 103117611
21 32174042
732 93857765
8 197800279
579 260634171
276 94682149
677 1000000000
671 189685232
331 436142468
114 55365685
702 1000000000
21 61186952
355 59845695
528 1000000000
229 215295907
11 10099978
171 84675815
333 31959686
412 63589913
32 7371580
705 20360010
298 275148830
226 147068193
52 77587787
231 140039719
549 41264969
536 277376456
583 295689847
508 730196900
512 183874527
508 30554193
729 15450279
384 56869611
378 17644394
48 1000000000
459 376556146
500 278992791
211 13562349
51 171738115
348 1000000000
566 4932292
652 50595079
454 66050852
652 80938140
488 1000000000
100 175904750
7 1000000000
699 366753987
618 338178584
443 342294762
600 75473116
298 297481433
346 79795485
721 12297820
728 265982141
600 1000000000
538 442687559
775 16345344
520 215834781
389 144058161
297 80226653
540 239254856
166 259152259
306 236401304
39 115886978
368 130871589
148 844328647
29 440334036
117 137735617
515 1000000000
401 498502321
232 19323309
721 19584862
501 35398737
222 34007570
210 223221676
349 1000000000
455 137626743
473 1000000000
796 434569842
281 745550
472 16014441
388 105760246
325 984099681
419 388018351
105 17480181
478 42134941
493 4807323
253 97272333
632 841987818
168 230487714
436 38746785
102 181660011
647 34117855
384 102945161
474 306643030
478 489599507
53 1000000000
264 236826404
160 35385672
6 1425193
642 82372634
223 192063005
517 391950064
60 748335494
367 463013558
454 179451999
265 45292599
450 9848237
571 450195188
411 172925705
620 1000000000
248 474691261
358 495502489
480 283567650
655 2010711
572 517750849
304 201253075
116 40477628
593 245365070
16 275826606
442 45502688
88 164872459
402 873864156
723 67626183
227 294131582
458 742805471
755 20091722
69 459166086
107 22856713
76 47513449
658 163478178
7 1000000000
210 77569145
157 281897144
497 19523179
279 20717063
313 1000000000
286 525727269
592 41017025
343 706828416
446 348189512
301 189974014
365 250835777
327 1000000000
387 64289836
748 59048832
138 1572493
741 12612736
712 193388773
442 101807103
486 483047509
371 112490072
75 283105387
24 4772359
129 277829702
720 9673220
526 2699870
740 265601315
443 38048054
380 46416574
368 154239828
704 48020297
565 80240030
216 321081659
49 221539847
331 149412494
270 52682846
226 13030379
50 1000000000
166 164353526
518 97946712
220 14848243
754 152374557
687 168685091
349 1000000000
102 166546817
625 13963543
40 5360143
180 204328424
254 481834009
79 461134318
272 49073551
362 425253146
294 55164704
621 1000000000
168 134978380
415 475997098
285 403134502
554 83872842
686 1000000000
84 770145080
163 37503035
646 9133790
676 29974638
39 6458065
441 1000000000
449 142877193
745 436575951
602 107638559
445 138695476
540 160130015
382 6377684
589 92754924
593 159750963
437 151544733
641 39999173
638 1000000000
341 1048482
750 1000000000
468 49322121
431 141805816
391 21244854
263 25850159
214 99580311
543 372714327
713 604951008
670 322310729
488 144460288
206 90875333
378 105550977
341 180077487
232 1000000000
476 839026
186 218649955
203 20511411
600 31021183
458 684630955
42 19327182
384 39776360
695 177433351
407 13704002
680 408317015
661 959932492
358 61037202
643 569217819
598 365530507
169 1000000000
35 241331739
14 1000000000
564 244538685
28 204926715
368 1000000000
409 423186795
800 475771594
654 347613487
76 885854873
483 82142678
508 1000000000
256 84844148
632 297048342
172 435569425
615 484196204
177 301290880
466 242409852
437 275962060
417 169945482
577 46358907
412 384546922
348 228972833
235 90783946
432 706104466
181 199069415
675 6592327
163 538932642
767 201363494
30 1000000000
394 151608905
555 140173328
44 272595837
789 148628245
655 66384617
675 438813112
537 29103147
732 238908200
340 53892932
777 121656406
710 143564452
690 47854723
408 916381187
703 234662865
49 376613732
376 67265429
379 61406704
548 1000000000
92 923199346
204 28727843
317 26600990
56 678819927
38 436239418
176 536133258
95 175171221
348 1000000000
623 126655892
771 138518634
512 211841765
398 169306469
216 30319355
454 75532298
800 146407580
208 773234586
480 231943262
119 388762501
63 32762214
322 117666929
615 1000000000
728 153635726
606 3581937
610 600190752
77 1000000000
328 551988453
476 1000000000
658 1000000000
51 94125438
232 95269751
505 237039231
529 19409352
792 173009552
790 574606090
182 68243394
447 1000000000
796 2682278
788 375582867
177 794657255
509 1000000000
767 367406740
65 1000000000
652 6364037
649 282493082
98 619746785
446 151394523
487 41305119
69 364247234
579 314327879
393 247020087
192 124312712
49 362643455
516 106502480
100 174972029
505 1000000000
651 561276093
261 167780707
430 8481268
497 279159973
341 3059043
452 61454024
360 57451943
616 96368457
302 73531141
643 1000000000
592 116270323
670 363541048
502 122984627
545 113994113
552 159082354
404 266419055
686 389309983
575 918307403
143 525022959
329 115035654
148 1000000000
603 1932556
454 608065413
221 22146358
362 25764832
311 125654315
555 101984216
369 207761196
208 1000000000
370 25893352
320 679094427
323 105599929
772 969456771
396 347389918
388 217297615
373 905491023
264 124616766
230 26034337
568 72022822
262 10093639
667 100819440
95 346198218
26 395960108
279 204338364
765 134029705
343 650533523
748 129667809
326 1208084
623 276005684
110 167657168
557 196323724
597 1272076
336 36988920
645 473723380
94 233463
36 542539172
160 13568003
506 238873222
765 105462197
433 56257374
351 87978480
239 109836419
492 189550282
478 1000000000
141 35894385
4 398793164
106 59887682
490 336226052
619 1000000000
567 94787263
248 858385012
309 183566152
280 15958580
202 125564357
52 277824263
575 380919623
436 38629962
668 186787476
416 227914800
521 139971338
224 248659365
654 208879940
411 99834357
434 4690300
635 33051577
126 998951051
326 32062049
218 48322864
293 135653783
366 1000000000
351 367209182
386 504384457
798 29347673
573 43145663
328 11130813
296 66434596
390 110156127
715 52627112
736 38473391
398 348791008
606 40775170
345 617025291
40 45473212
627 148994752
741 508805360
230 485731406
606 93799414
344 1000000000
315 29323897
466 94432471
676 957488434
251 30368597
289 88562871
285 84405060
761 45023749
446 534946887
694 16122860
232 28318877
158 90511935
449 495396430
762 854588
529 1000000000
81 23360492
642 14986368
365 196171910
346 1000000000
404 405829220
131 122627201
175 139645308
643 145683458
486 244583822
323 63101000
97 289312512
42 279360874
648 346327546
98 176835193
354 15670405
689 182138171
760 298254622
224 1208132
338 227695891
663 150865660
344 141099183
702 114260188
306 201981368
765 6036562
423 224728241
443 69887509
481 195630811
641 1000000000
422 23141552
759 13157845
479 1000000000
517 1000000000
531 21625433
403 246764767
684 118265518
40 27910073
48 148388794
429 311247712
552 433995211
234 162998483
572 128516161
391 217023736
84 192278806
108 339504614
664 312916084
384 1000000000
431 16150106
13 122153014
546 38514708
505 133155645
537 113331355
365 241564568
604 557680
368 1000000000
531 422637040
76 315448648
133 199685438
711 14860051
732 64394059
651 251352778
702 574605371
702 214219513
692 73444526
136 1000000000
421 204831369
115 161646066
59 357137199
485 1000000000
732 549499013
680 38869909
529 17763091
130 33484318
130 380882791
636 301340228
471 376389618
29 57084289
376 326918796
623 190222954
492 1000000000
184 1000000000
124 47391972
577 54410921
112 184587716
530 64748176
80 280246634
563 10318558
228 247989341
716 320778360
499 1000000000
420 279432831
359 15701735
356 31952761
742 1000000000
404 811273716
345 157714295
764 88301610
103 145062996
196 407268052
26 473986317
691 90263802
344 114962027
434 100639582
554 40116785
41 75793162
216 362031079
192 126520037
426 151427480
703 4297526
648 597885230
653 54134574
409 1000000000
532 535745782
134 1000000000
570 19881750
87 1000000000
104 48827956
84 255531229
357 223211253
37 173007552
123 544405948
17 250213122
720 1000000000
226 1000000000
366 246597051
670 36893119
603 90558643
558 61672973
383 43919520
121 248995941
452 168251270
617 37268920
336 130419926
4 53634
653 67375373
595 57669526
417 147311236
606 1000000000
341 180063822
109 857050104
112 13916493
392 325841201
60 218774517
150 80790039
191 203949298
288 1000000000
418 563976
14 367353262
781 460348894
392 392031163
488 104987312
342 14501823
475 115339022
575 176569224
493 177711809
525 302065510
647 44912833
326 29550966
177 83152317
51 213128147
755 98198597
667 180951441
309 317557549
648 328349467
478 490851316
256 163889590
599 126053824
780 1000000000
296 230432897
148 398294948
633 1000000000
96 175226
722 553990400
280 5566788
666 47219526
739 77506612
411 1000000000
330 251984766
603 133439813
437 35913868
259 109078904
460 227682825
795 98763113
311 28300226
650 63708832
669 168076907
729 168901587
136 29666081
177 98034199
318 99773795
568 173445677
712 112333037
470 599928159
525 2469295
469 443910727
663 185037339
508 51247297
236 561641114
146 162226077
85 322891857
192 36035880
666 208773895
46 454308761
771 208072797
675 345804635
504 151266995
361 184762874
352 287683337
422 183626202
100 22455926
195 31832265
108 49635922
200 231730853
672 1000000000
61 129470933
104 1000000000
298 84662780
363 28656689
662 145244548
499 163314083
586 22283389
742 451842275
238 88097224
173 183349901
650 8452078
687 652744198
774 121034921
630 758734413
777 29330976
328 1000000000
380 398688078
462 155324239
327 1000000000
112 1000000000
242 54826256
502 156252943
197 5067173
456 111600973
7 130733246
205 165547293
322 559011370
398 87003657
28 317955610
211 404556154
318 194090821
644 655120196
656 73932753
169 285921358
377 390201811
265 184375237
738 443583969
174 258583171
788 110256862
478 455332706
469 203459085
418 789226
493 168180772
641 4536030
294 382895544
357 58965858
39 194594411
116 213815336
215 291404949
215 535138476
191 70473793
246 1000000000
423 77100767
89 180228708
86 76599382
104 84538739
86 328430126
586 760898692
493 338322727
104 58846538
580 679466023
298 141674003
67 188740603
760 160597022
434 331090835
698 192826383
185 41159510
535 1000000000
607 179826336
409 1000000000
141 26845362
614 253697860
523 83174837
327 763717776
321 123572127
227 215331985
503 62755071
68 444573919
788 39888202
400 605247706
705 58900698
208 67987149
70 61542401
172 133872740
779 34770849
236 1000000000
24 69925755
696 195813852
468 1000000000
55 472681392
681 264498831
498 48208984
157 307071156
433 380409689
441 381291336
572 1000000000
389 109177724
187 123773958
168 176705018
117 1000000000
235 1000000000
52 58899519
695 114899980
638 474551003
82 405839903
700 1000000000
708 147137171
341 302046157
535 546764
51 158200524
178 1000000000
540 64732336
700 203211757
153 136452248
222 941777
82 1000000000
64 198365994
655 61860812
617 11583029
632 133329525
131 295665774
500 74454162
596 115369550
300 1000000000
389 57703568
232 1000000000
670 2605224
432 12731754
551 1000000000
364 547395286
616 1371074
675 296545377
72 77440168
223 425410121
464 19271154
230 302942840
648 358150901
513 427191004
504 126557718
503 206033350
488 1000000000
50 121394871
319 59434772
504 203028632
550 157615945
338 322401810
69 42357146
328 356437338
388 310231690
674 311588817
427 87670812
72 494524385
129 39254593
769 403556635
464 18487173
694 28229950
126 378613379
271 177543
788 253218124
244 770294480
794 216950149
141 855734439
631 52500193
577 426778197
788 120557887
698 76992890
346 564297810
606 5722526
399 520475879
726 117179909
795 47642566
73 645594511
552 89353236
385 92160105
637 128416415
36 183527275
1 468463636
123 8118687
637 121843792
718 1000000000
761 218015133
549 45316096
316 1000000000
232 25312282
752 1000000000
30 1000000000
635 416695074
784 1239424
102 79895118
486 278791326
537 147283958
360 107608586
412 158203778
510 218246073
759 247683042
143 56343917
81 348516497
325 144511528
499 1000000000
454 101235759
421 97119992
219 169520059
111 326787531
587 370364426
313 153225733
160 8764951
650 197913582
64 7499857
651 148765238
532 39889116
772 30458253
100 1000000000
317 215117468
664 443427320
158 88457955
664 258212442
782 177831801
619 351869995
759 6504283
634 481321105
447 484404618
749 2154768
143 87199917
76 1000000000
47 494408301
511 1000000000
166 119934630
77 46059023
414 113066429
800 1000000000
669 652340005
126 208318721
108 173189219
16 428184671
659 508716766
285 7335820
345 401652765
175 80938152
520 42849431
268 1000000000
422 500272677
157 590759776
412 95641051
266 37592670
498 5755372
123 990102729
719 69090861
152 11267078
61 161365853
424 42761054
482 102779485
628 811062229
487 201778951
612 56828958
628 59135953
608 127569779
721 1000000000
464 562146824
390 54303336
91 392236584
666 8547905
331 74290757
342 1000000000
550 289452992
98 81816567
245 217132665
742 922454517
671 1215743
10 75427183
110 68951768
53 906746368
168 1000000000
688 344596655
534 1000000000
259 59244617
736 44899087
22 369607344
302 1000000000
49 28346506
776 111936852
635 31130013
245 735229211
222 422119415
542 20905554
736 28335192
395 219973810
618 39648584
452 229840770
228 362135
401 92841677
373 198165335
441 477112417
135 26285780
6 480527343
64 297497503
766 154073634
617 537018528
746 331610487
618 96423723
593 88064142
522 164620450
29 200473115
595 392360568
500 1000000000
427 447432918
479 9850613
379 110256407
678 157398861
139 26765633
689 258435260
610 731747612
200 1000000000
746 15249427
690 147121626
521 328184192
760 61760420
488 239980071
674 11083090
431 9682964
792 18895839
486 26640667
258 209974668
213 183079231
263 139605393
131 6169953
337 24111270
633 78197902
646 259628121
191 32326655
239 1000000000
765 14989754
403 180545277
187 846906938
540 360079799
480 35225297
752 257394905
277 510068859
248 203801191
2 80669638
348 147484210
399 615992577
228 19848678
548 143503809
440 22227301
232 245415490
703 15300157
389 13907424
130 124046657
673 117705052
233 28088597
293 1000000000
348 8991862
313 57705100
35 37657051
772 138482131
197 230818563
176 1000000000
716 21747585
707 305781226
254 35893058
646 262045040
356 307811376
449 106754278
101 253063515
411 247853625
715 8485405
542 1000000000
124 372489721
240 208529129
257 17593278
90 98107485
418 373479536
772 189942046
7 1000000000
629 201269001
760 24192113
119 116035478
796 255553544
784 306887043
220 25942242
233 389494892
32 368373025
458 640341930
16 187633985
539 463576087
276 52555080
292 370679448
499 54010539
76 229072834
311 5401114
348 1000000000
390 148024554
28 430015684
201 1000000000
116 458204951
711 445363453
684 125066860
458 74490496
299 433008441
24 157156324
666 236132690
186 97189710
545 27640356
696 160351204
392 1000000000
218 58327582
439 110225649
552 281389867
277 719429796
233 270703730
620 61082019
294 712072134
322 156274021
263 191323307
640 114859576
244 1000000000
78 707830831
149 260598611
371 1000000000
209 299920169
569 701711347
786 214063395
518 1000000000
318 21148092
3 105912073
606 668193913
88 495031605
25 152473604
364 280231842
409 197048505
745 73131681
708 695692769
245 132702793
419 344774123
153 4124287
702 77254991
285 4269056
765 470628520
392 23565272
424 396140470
548 15455455
486 755361250
695 10352686
192 164808569
458 219718709
478 260228681
677 184311362
616 27677986
400 82210168
518 129041393
467 1293937
383 7365418
757 219368992
477 152557404
191 1000000000
518 754101420
121 584627384
3 10367114
363 395612
91 175690582
349 232831667
184 435095411
22 276393916
320 14610637
383 60851048
796 90114387
192 254579630
436 358396511
737 199366186
688 228989359
650 63164041
472 244174160
675 298747382
243 1000000000
531 525477133
298 35089735
131 94057789
101 559912888
443 266001525
268 185804541
99 379547916
679 477907752
66 32374
669 100923279
450 133750497
152 31954479
233 162280397
30 953304763
64 339096039
56 658777783
495 250461304
333 121552997
317 492898983
359 19935742
180 135820552
492 43396537
634 49093162
613 9319462
632 440203577
410 68078202
438 304119417
403 1000000000
604 204947159
632 26501434
145 113948022
48 209145099
382 76143559
260 1000000000
587 2741049
508 103493633
800 89538884
416 58918086
741 1000000000
184 844668551
706 590398611
331 1000000000
446 47585352
3 543160971
194 1000000000
70 1000000000
598 3699164
285 1718729
226 118506519
527 547598419
654 419347186
422 532207337
641 492518347
584 1000000000
228 348600922
286 136730453
223 348033520
752 1000000000
250 1000000000
550 838064039
733 1000000000
136 1000000000
656 778848006
637 20992382
634 1000000000
718 313131139
132 1461639
611 194007174
310 242815969
452 192331236
504 222002106
601 1000000000
337 707512900
297 232797967
331 89271304
62 30265563
172 24473596
702 310823796
445 106943164
146 177700857
262 331763425
1 406725650
494 55946240
341 16409718
223 1000000000
308 330209856
159 29711453
295 220676614
87 1000000000
118 102317847
687 84254342
681 594103319
687 33025434
776 448491290
702 164612234
26 14082293
581 1327381
296 1000000000
268 561328667
90 50065361
283 1000000000
600 3947352
346 164451392
586 320885532
497 1000000000
599 257987494
359 233577978
777 26447927
613 4740307
198 297734
179 71447407
439 730729472
153 300615562
163 289189137
767 185241300
20 38675672
524 12449723
592 1000000000
265 50915174
160 178782489
702 1000000000
748 39724444
243 211700099
668 71707217
16 1000000000
632 169059725
477 50664396
615 68264332
769 215898870
786 1000000000
709 22224831
769 76159750
17 44867271
604 272681407
13 1000000000
427 833903151
544 663341482
213 161056812
788 4515630
484 200700739
271 151543702
190 236235903
410 392341719
748 125963907
701 166645278
501 711985335
383 268359429
771 112405594
586 22343918
572 87028300
420 241093567
713 37642212
86 1000000000
722 85519483
168 396411111
639 147849849
770 111867458
696 36134302
43 129573364
100 215965694
236 46818219
172 239129400
557 70869456
664 9348750
22 129083998
80 0
719 1000000000
668 86999270
608 25173238
259 204531882
208 1000000000
111 267000619
744 223623778
262 3441562
688 1159589
657 4633827
112 501528498
279 1000000000
144 96095291
290 1000000000
215 100994040
504 256320480
462 1000000000
290 4229734
733 208083536
584 31412639
748 9523218
594 2066479
451 739856989
72 443657341
330 5896636
369 163706833
616 182308435
694 201110313
582 38706455
607 87966387
204 21081160
756 392546851
194 917755988
509 1000000000
303 1000000000
609 317419959
797 18728494
778 1000000000
178 8738310
254 1000000000
791 229165917
6 229434996
756 25100792
9 103781142
80 254907049
273 63029086
597 1000000000
324 11656199
329 380828726
491 676288953
533 263777288
334 156561729
257 12157757
533 46282316
277 21373333
424 42420855
248 1000000000
430 446769106
563 68238083
240 511186426
622 269362592
118 821855831
113 348331803
72 73459715
4 18028647
174 146146268
591 997849
335 916033378
601 168434868
437 1000000000
491 280877499
486 385819337
717 67488259
651 164968584
71 8572560
491 1000000000
257 525505357
656 123904621
354 6561877
448 439809103
531 1000000000
260 205832699
701 195142352
36 258958993
357 258686481
776 46078890
246 714228362
216 234698596
567 2397339
347 34890864
207 354710557
90 28249225
583 21447912
509 553215125
391 37586660
748 16701772
599 227266508
239 123460167
190 37885670
333 415894980
518 599113092
272 1000000000
309 54481990
446 305364930
84 969649655
672 46549583
267 270079670
253 80712732
513 11169458
255 64371213
576 141657705
172 82145271
462 191194344
750 8377470
532 364433972
42 543439244
698 5849964
491 42463963
104 406201156
792 27085474
165 96980109
440 13886584
730 344778248
468 461743503
272 4760746
533 130212615
12 234188987
576 66186388
793 106147838
192 190903167
30 1000000000
539 1000000000
738 335229697
667 389262102
110 25263506
70 765998877
682 28026115
165 60733109
478 2755322
319 191580902
178 53880793
478 11028242
109 1000000000
776 374955555
184 90973266
711 1000000000
28 45207460
736 17342380
286 197228777
30 108360827
745 15269887
232 8559753
772 2579694
5 1000000000
86 204760785
286 215714043
424 913061235
636 75008407
162 129158388
484 73209457
44 325934844
449 74951059
45 841761584
665 111635812
111 194762967
406 301971018
56 607644982
446 18075864
241 1000000000
26 414341485
578 225246660
657 225710390
306 191862640
301 21375875
459 14480084
212 58082498
243 1209803
592 202407990
147 258422357
774 143709723
307 13829108
609 19174949
219 338482220
424 1000000000
626 1000000000
610 331960764
65 177803447
696 41150678
657 298720239
275 340360759
167 477441352
408 768912938
110 57054084
786 750695195
685 219891721
679 932089305
459 176868795
97 705822
433 44850932
358 23272223
103 113468507
479 863835861
309 75159573
627 394838298
451 340915171
588 202235486
504 959595369
272 706612906
125 230260754
393 1000000000
763 179597925
508 115695659
727 229922128
340 476676314
92 1058243
792 402545965
337 2167973
271 62166573
797 439260813
2 50636234
713 150404924
762 142617049
445 249053
124 343866716
641 311611726
435 60220169
604 595808
262 213823355
312 7441825
796 195726254
603 94523247
30 720843764
622 9239869
564 27920800
345 1000000000
774 89609105
771 434399834
315 271219094
630 175469218
284 353660032
696 88749053
498 279383362
338 68287716
195 1174527
332 44894128
23 121362807
718 258651923
280 233605893
415 69250182
652 510698250
136 185855956
637 396377902
690 559428412
49 124955123
162 51974518
624 221301748
195 135334138
68 454705731
732 185248317
532 125920605
724 956589974
551 226952055
180 252202272
358 1000000000
452 269357667
633 49980637
76 673758060
776 1000000000
628 202691023
442 1000000000
131 1000000000
376 84103919
482 1000000000
43 723712376
730 181083953
441 7546624
304 1000000000
394 520139688
207 110402452
232 607771797
190 82785889
121 286787910
132 354354667
167 417578467
394 233635357
184 355862948
344 10625381
436 805234845
598 89748406
645 1000000000
171 5259189
690 8466854
577 1000000000
546 37108371
286 194159714
414 225440375
651 86299393
334 529213296
400 219633468
122 1000000000
596 199807913
457 204789140
129 71313297
420 62920872
253 63564990
436 1000000000
273 1000000000
607 149858024
5 448969915
237 467909232
33 72091664
200 201650443
748 2271565
246 9723956
271 124981206
769 33956500
563 3086562
431 215790104
189 76616061
168 239625622
696 150478513
470 554078226
331 105313315
768 1000000000
29 42874939
397 251363722
119 66465879
294 5311989
193 12807535
147 9607627
355 298211355
380 58657463
645 124002974
360 50063863
654 1000000000
64 39469605
712 262376074
205 301785686
441 1000000000
725 6848101
329 862090731
608 66175426
674 1000000000
440 43661908
139 161963680
227 88978386
619 1000000000
235 32970350
11 611879395
150 160301788
83 283412450
364 271308367
555 35691624
567 16101483
666 365641175
382 761879806
362 334864815
648 160290904
33 82052132
638 1000000000
456 235740743
392 109082075
519 60503124
622 46710674
549 201109749
23 297715148
172 35949071
108 6383893
2 10466005
54 553837751
208 369098081
315 12022016
318 147575928
451 1000000000
20 76005710
152 224271879
25 232608209
288 167082386
22 146781149
293 1000000000
532 158528592
237 248672045
505 1000000000
704 90649635
429 133743678
520 296196217
474 82547771
76 45732365
646 73533258
499 856756747
538 3552020
742 296423026
478 50219143
653 1000000000
794 84926630
112 388535129
246 121427790
694 52970164
761 97708580
584 30662311
205 281631697
463 134809277
344 37180921
17 354034935
322 40752393
790 47956504
789 245313149
648 172433675
24 22666464
77 605816469
274 44757584
591 957669278
300 1000000000
468 16730364
526 276707964
324 1000000000
800 12407014
137 14381850
169 42403438
330 196593147
531 146790714
398 61817654
260 21901557
62 973930
357 508238567
738 614468691
94 247026538
642 40657235
150 14825910
773 50926289
471 4017604
724 379603446
391 805050802
632 707982266
495 56051268
439 26854007
471 1000000000
761 85300252
7 49075826
616 206492894
134 79535651
682 30421392
733 66356330
137 1000000000
53 785614076
779 94826815
20 1000000000
568 461664419
770 6595579
474 107542256
265 96708968
632 353755907
367 479906955
281 275458810
765 682911768
262 337898890
507 88803598
711 5705944
145 376540644
164 133820497
391 21992600
740 358772375
388 181145418
368 1000000000
530 27071319
689 8152854
23 7249539
749 440520181
379 26791876
204 24801177
296 275158854
408 1000000000
261 301652823
503 471558118
249 644129524
499 507935226
749 423889106
18 102522764
617 68502164
220 9657488
309 307739904
283 1000000000
280 413878545
566 5510175
156 164379269
180 195743245
775 39322693
318 197081505
290 122169188
604 147894840
85 147649656
22 176036191
199 37554020
147 416772608
34 83842245
220 49292067
428 327143089
154 63221836
142 372636588
51 146698640
272 4041506
143 794040710
314 147305026
696 4880761
627 330368680
276 172305948
708 611457579
77 632509631
470 162932244
617 20189563
111 1000000000
240 260027851
343 70224726
460 144540778
536 32510053
772 935101
536 169265519
127 107950469
768 912475653
550 26772258
664 193305736
705 399558919
488 1000000000
472 203333763
376 44811433
626 411176899
527 1000000000
536 73571781
759 25152155
595 122309864
470 952722327
9 49345681
276 72267575
514 90480425
347 31089168
264 133917745
530 432814132
545 86962477
480 137277762
151 304291416
494 1000000000
784 53731879
580 200952781
532 739103367
586 71018630
685 23154671
71 277448515
354 55341486
485 45878635
666 38989901
74 68383841
190 59010512
511 537721108
246 38393779
748 362871211
394 46249312
632 205919512
449 1000000000
237 142673427
260 70580825
625 4976947
188 11352592
13 111196092
751 249372320
265 158976105
517 303460560
621 71060388
8 37712531
768 1424558
606 33933127
459 100030328
433 77860625
23 243934839
455 44810755
746 46300832
328 123859719
460 45905897
510 165754614
615 487139316
16 416134059
97 151773141
261 439720
579 150164348
678 1000000000
693 134061890
155 88849805
415 39413236
780 1000000000
201 203467399
544 188610422
58 1000000000
384 115756048
412 684213318
21 758861446
117 253082113
37 170753306
238 1000000000
152 1000000000
782 57811438
632 786916262
415 72448821
43 307822948
679 1000000000
123 42230978
47 1403213
430 217052044
543 146757637
492 1000000000
543 33837531
799 4836476
182 103963684
174 6182354
14 470970170
288 29344028
557 65458111
542 1000000000
124 1000000000
368 77885570
579 9596582
734 2128322
201 241572788
719 276154866
56 276053132
236 429561193
726 216951062
350 64890389
236 1139701
427 270203437
386 504783395
123 175009508
768 63416096
600 96798809
589 507507129
776 1000000000
755 484244951
661 1000000000
792 1000000000
549 205076386
5 76295886
672 106436713
129 836000113
48 39415494
22 408992212
668 711244081
586 576138828
171 337749145
134 19819066
390 111860777
338 277209150
245 79053427
598 45634555
160 104680035
58 59439788
142 240019128
517 179129114
392 69292228
481 59899250
375 406926097
372 15460757
65 1000000000
263 260843082
558 152529949
705 665742337
776 17367389
620 890333012
53 139071722
750 78244403
95 33334710
592 260296325
620 291894568
122 27232665
548 80536529
596 112673756
433 56624
165 541860705
314 1000000000
631 403394762
198 9856289
400 130123363
670 30430039
409 107139910
10 472054384
58 86819807
146 21309047
250 136751399
317 1000000000
131 104019515
180 256328631
315 209914131
448 72789481
459 138489932
743 483113886
283 14457273
433 33026566
563 164791840
200 66644224
346 122173171
754 474046281
506 19014309
665 89134545
697 673448496
451 74469008
256 2721096
696 27391829
214 145862944
34 242057800
741 1000000000
392 183022824
723 1000000000
145 859303092
777 922422332
774 152632685
143 1000000000
463 585550251
685 1721879
244 541786747
11 266690925
348 34414792
720 17229441
208 180115606
390 43042792
665 7586099
467 207471753
61 1000000000
512 410648967
4 1025502
724 6328796
56 170550811
665 122721096
575 1000000000
789 55339408
163 112672660
305 65196026
234 48783824
597 1567010
572 92328716
713 287206916
387 111324533
52 898518194
262 140538697
32 46266947
12 1000000000
627 16761863
574 285357864
22 1000000000
356 181085784
465 500976800
454 14323626
651 827063370
747 445062017
206 334934224
605 83879067
192 120193515
130 297067824
746 1000000000
515 22610511
436 206507502
135 620286941
614 56631334
632 244086424
103 113784439
412 320065803
193 1000000000
157 113353172
474 508169011
353 277029592
59 20292903
305 350094810
75 3648326
180 36982845
564 8893896
564 112465743
700 73868841
503 57044441
492 81066444
262 467084713
684 684699605
425 27156937
484 63701542
648 1000000000
700 337714780
298 211855472
571 1000000000
409 324128783
715 412191125
635 1000000000
626 189474755
121 3884873
409 159469191
698 504317604
519 14343154
8 17079776
70 869895843
393 192966611
732 47313935
231 63278589
626 4009865
616 269558155
400 104584941
213 73977675
670 28841898
405 182629077
227 352835827
658 410170624
201 1000000000
754 481353607
470 51334733
638 123367584
19 84264265
158 1000000000
72 116108765
122 820375287
316 167514954
601 238561236
185 21499100
645 343316616
613 7490405
292 199844828
169 361067611
287 56802013
525 202890745
669 417848857
25 372879748
136 305480363
436 37360940
6 232466707
232 112245430
257 123223462
123 401493405
383 338691387
310 7286211
9 127080130
640 16960793
422 1000000000
515 274794089
96 1000000000
5 1000000000
541 206327648
240 555384991
550 1000000000
522 105393347
259 57740413
283 676720175
348 23673051
493 112047396
152 1000000000
422 1000000000
705 78324825
176 1000000000
797 158095572
17 1000000000
373 83384034
402 592214824
304 1000000000
538 155957701
536 99128481
83 14135950
307 161885117
739 1000000000
11 756271549
563 12597531
454 70750417
171 407716969
525 100740047
307 357072795
711 1000000000
274 1000000000
702 173473405
146 8632634
568 106194643
505 34212134
382 25913975
80 46286264
536 7377218
287 579382414
110 190957341
269 150767950
743 436517128
580 406217818
13 630116566
586 412960038
6 178883254
72 197602268
539 97695139
454 244436372
211 5104317
620 1000000000
184 116782627
673 184190123
432 52725579
559 170029718
101 10775720
796 6994746
605 274670070
721 102450724
449 61272718
661 152191853
120 1000000000
658 97220839
12 19323143
206 1000000000
451 46168423
83 32985792
486 447765999
711 133386160
765 147296378
434 100312821
560 71326444
734 284512642
166 108052668
305 169403480
73 656574427
789 1000000000
31 3180777
400 126977114
273 26641450
619 4637964
6 186646439
749 34909963
40 108508903
480 154666316
509 146666635
202 102486619
687 18320093
116 96084820
132 327008654
166 551231420
133 58437383
72 1000000000
601 6728872
545 5591828
426 146228883
315 488523855
542 1239025
220 385025869
574 765367474
141 2375338
178 1000000000
406 19771200
482 26353714
766 15348024
533 673471111
175 891415926
181 66189379
783 268689230
104 77736828
231 121500885
87 19251326
767 307145871
41 235783383
31 7563686
8 276164
46 52599563
570 407926658
118 241969724
297 138418552
445 304633969
347 85377654
44 14966796
473 511394244
10 568056933
746 1000000000
481 1000000000
120 53020138
151 232287332
585 181426459
214 194241805
294 296630725
100 101227820
471 40434455
649 90059484
164 1000000000
399 26775746
532 12226018
156 473625829
753 742785797
442 1000000000
513 102257527
47 970242842
461 198510116
484 1000000000
508 437053345
64 18563098
88 87073267
77 34014167
487 44387695
81 601504387
339 21621601
277 768659216
450 1118168
1 201881911
701 1000000000
509 244507728
747 34953999
432 240500259
86 240198843
356 426716156
388 142574539
383 453562295
638 969350
394 12674221
556 380546611
653 198270200
790 103534939
367 351588508
323 31836750
314 299517973
541 46106872
404 147336231
138 113450379
358 15643540
595 1000000000
728 294766524
607 45326313
370 242416770
632 5660134
603 320836579
772 305548649
605 621090612
493 337810155
158 55201300
697 30783711
583 54007294
241 1000000000
383 643848171
540 378973250
48 82443499
228 347047988
448 1000000000
335 31103397
121 117845163
134 130763733
449 191186652
17 324560143
416 95159442
440 52147287
480 86662364
770 449471290
295 441719046
249 1000000000
415 86919633
323 1000000000
174 458839731
745 58599490
29 228485850
338 161173319
467 189769057
200 15076956
90 224919057
497 801960
536 8623248
567 16518022
182 13193969
224 214853139
668 86364883
757 39436739
594 523482
125 671347686
223 20927543
2 220022216
461 80948872
458 33749731
578 2311424
734 382354703
167 257899384
518 140325036
420 18031524
522 40336118
640 342591645
497 88992876
197 1000000000
261 509955516
633 190092083
44 58906025
5 287979487
623 114358012
561 160560644
533 341151021
549 205597412
72 53069043
552 929349337
782 40002216
708 15473829
241 80140942
319 113450212
87 357642121
98 1000000000
169 93016105
628 1000000000
622 129302341
607 110645347
80 307871383
489 40001093
565 64619454
188 560680705
358 432827550
30 18125273
363 503082131
183 207906600
556 80366602
337 67430823
656 36475035
82 490714658
577 90965264
324 159812826
69 311430956
109 153087049
421 1000000000
662 1000000000
680 776779441
70 79626837
24 542853685
519 702876
283 309542745
191 173838859
347 82356367
503 19300890
222 18820588
759 54248450
333 54045103
775 51110518
399 416700739
559 416845671
110 625487135
662 11812621
528 40355310
517 365354743
414 231871322
548 793213231
64 1000000000
507 109452796
670 135694788
562 2769540
607 388248893
688 1000000000
749 86551372
254 104050111
110 284000050
708 392801357
203 35547066
10 175751582
236 1000000000
728 130971624
184 2679593
725 503776813
697 8141271
203 325217605
213 14477043
640 92679275
245 1000000000
509 106516519
673 102527337
489 1000000000
416 1000000000
366 503834234
764 128601669
530 255773617
539 487860765
511 1000000000
518 42684661
763 4146994
613 40734668
590 66159697
768 22891851
162 206531870
190 233999744
413 50933483
745 646980905
489 127089959
295 43903900
524 868196442
513 880571358
623 33041760
31 312553823
153 319753102
584 1000000000
20 33888148
38 33510944
358 292825927
543 447420637
728 31087180
604 1000000000
498 500300626
741 103986903
796 71261710
289 1000000000
286 1000000000
794 3295722
63 411319689
662 65575180
648 366053536
30 903810210
513 995086246
26 26054812
466 13486398
306 88855644
643 264645500
397 38021385
315 86455875
533 111169000
387 322005704
336 112742708
611 15917690
71 190611809
675 276973185
226 378172216
75 294144000
168 155915777
706 536802554
451 93454812
146 168583960
505 55759504
513 32184856
403 173386152
440 223191638
25 12570033
414 363984917
594 199504494
477 12273061
136 72695522
219 216382630
481 121850852
578 100433374
422 512582104
696 32627597
511 295711118
741 215872995
468 396267455
595 99513030
428 79140441
168 1000000000
657 8409812
14 405376930
137 84306704
363 115363160
573 1000000000
104 97512865
693 481959155
652 490900306
216 344704397
129 958181967
528 306399095
45 109950491
707 1000000000
121 366200724
602 49084217
269 143388824
765 139610313
401 1000000000
755 244589361
621 22728871
486 82042314
712 1000000000
732 117347684
619 386385447
574 50868226
574 223358772
564 13854672
393 800031050
646 551008
788 29685643
155 107275964
198 1000000000
541 597038645
168 216862221
338 33208596
770 1000000000
611 12486342
636 190944036
152 1000000000
222 54547111
184 1000000000
175 161083394
461 7279084
537 208418105
701 248978081
450 66903674
689 65629691
595 1000000000
113 1000000000
595 128964058
548 12474085
108 1000000000
308 323130314
772 2551883
647 642967805
229 480199164
326 563124629
21 495063405
217 160928294
220 178926104
392 315361536
196 312623832
762 148882486
723 19047617
537 221048277
563 148288849
11 10369302
138 299565152
505 181847259
769 58676665
11 102866091
799 430012808
232 695954923
302 1000000000
186 74796454
340 59711699
583 57823042
378 190932132
408 218221102
744 8346463
789 117799107
294 231456403
133 69454262
604 287667244
626 55290735
529 23262587
162 1000000000
558 112372566
606 201389016
699 475852212
462 22356127
96 66478900
794 184513354
645 314744816
41 10262493
401 142155183
325 303287355
269 344405611
660 376087767
513 31281216
799 420601402
277 221387912
718 291379469
721 187319153
584 1000000000
540 64339018
759 17424431
384 437322482
1 176581761
99 223082618
463 1000000000
142 235721629
169 168366016
553 55790027
182 181967935
315 191128444
320 491002080
749 26255601
109 374497447
200 666252505
710 647331003
146 66214712
755 258530607
531 3887883
380 65951197
789 19365097
200 43023803
415 285812502
257 160789747
312 341678005
749 119196925
297 371969981
373 18389008
698 331411975
513 657828743
306 91301717
216 546870945
27 1000000000
228 74575285
283 26908577
715 110365107
699 45346765
150 59170942
643 3458210
717 26612682
91 775077727
535 453462667
203 17925824
318 827516
442 58481334
424 138922434
209 338771407
574 1000000000
184 4721876
296 62958317
791 172712175
334 145383277
726 233238905
119 1000000000
92 974054260
653 410945593
594 43020745
54 328819255
160 884227062
475 200864528
110 335335667
36 362121665
260 59705102
120 200738688
73 195035530
641 699940154
295 160368989
165 296592345
324 181946622
461 424867242
41 24659905
705 152904433
766 62138495
776 144217314
490 459103144
396 158257451
310 469877091
371 327027016
139 78279128
262 1000000000
687 761502729
237 697865051
298 19726219
144 183548
230 228106927
694 16830036
490 136712749
521 43557674
157 19684249
239 95798024
680 256168249
529 295843044
339 371130404
695 84352074
197 123549084
136 173774713
552 226980440
494 207106763
514 93781297
111 25652140
540 129309798
340 202878814
606 10543163
229 52524597
560 165491457
649 145100432
474 855808803
714 197687835
291 1000000000
366 251091672
340 97342350
478 531461793
661 97057809
546 153610957
494 63847412
674 204529014
199 22492526
101 151544980
167 53006385
117 56811700
87 91187232
472 95974583
511 734971035
119 18757144
39 342715935
90 278803251
567 59237177
456 417163047
278 202223048
779 384027127
590 37573309
137 1000000000
613 84356298
331 745513269
708 1000000000
121 497746012
499 59315721
506 27397217
601 1000000000
664 129960713
479 242077457
601 1000000000
750 54159627
422 393754690
236 211012335
199 26374056
641 116716776
516 704707716
791 108221125
36 1000000000
437 478656199
81 684739479
418 233583073
17 1490162
295 331998097
781 672875087
364 399296622
749 11161712
440 43832146
728 386420969
437 556148926
728 30564411
617 356087969
243 909912748
349 340509419
306 485877221
409 265692620
605 1000000000
773 394679472
603 21055171
425 81014376
54 50018092
748 56387713
532 1000000000
279 122695591
798 201709898
562 232946140
444 289658338
581 13920749
662 297556390
56 77823921
83 564682855
658 96525352
189 306155614
732 578432270
634 599778506
638 383760849
435 285678323
416 297204448
80 363215647
554 6070970
280 1000000000
355 3960074
629 4244419
53 66217823
141 250283427
262 209360228
713 28106999
223 147152537
401 177119971
40 78245896
556 614529636
648 222153617
580 170787289
232 452074150
31 17741002
209 113414033
230 99278869
777 869672318
513 119204973
536 99606311
728 177363288
552 341814824
498 222800002
224 684917919
729 366744528
743 747743161
307 84598837
454 407029768
745 861152
197 5560470
579 67288673
139 394590459
104 135514304
482 217523456
546 76276908
464 172031998
279 1000000000
446 224022403
400 71850771
500 255804257
85 3770824
282 250922974
13 11020284
312 296925657
354 168514570
725 988411273
122 110575041
410 17434347
190 1000000000
175 1445356
534 257793252
348 111157398
170 134230537
201 51186771
289 234857077
317 1000000000
37 12304794
577 42095671
348 57629609
221 46961643
783 540241664
473 62142252
38 1000000000
61 43249992
168 97822781
80 30837227
287 580280540
412 438268422
113 181361177
455 37039616
71 88616968
762 158412689
617 74314748
61 7034612
734 268101612
567 245319575
592 56967587
18 1000000000
421 33121417
340 4676850
134 139044554
262 4861928
475 7906938
304 255177646
300 1000000000
89 20800671
320 347865814
491 395792226
737 1000000000
716 662659532
405 85959109
517 57689225
773 1000000000
542 470517134
793 389169424
158 82666795
248 1000000000
111 8302768
652 209272198
183 1000000000
571 4860417
383 190812358
366 22238426
751 1000000000
77 4533395
559 756591037
575 138545228
327 72256239
174 21145998
638 57971779
320 41707225
669 303912284
350 178870984
268 2957214
336 3666296
691 589954394
574 389231941
474 1000000000
303 295544622
680 305442113
493 699440282
38 146799752
542 25369556
316 145288545
683 3723716
242 294051016
348 158628841
688 59187569
568 58066230
477 1000000000
9 88597380
611 251684046
213 9131081
40 676545939
37 55066448
309 73686945
289 151421362
306 166809079
48 20901198
422 7920854
764 31177747
635 78876303
651 2094591
343 1000000000
646 543466133
131 69379264
437 72418639
263 220353109
576 80818548
74 1000000000
46 645490977
630 2455617
169 224345589
593 41851929
791 137414656
676 6573904
33 156983542
471 263299182
175 397778317
657 602083416
424 177643374
572 443194895
310 5815281
222 196701841
703 1000000000
128 61346786
588 24571568
618 34545321
677 115855106
324 535170722
81 135987240
214 1000000000
762 88438240
359 28902370
6 18859408
800 16038059
318 44917214
681 41584788
10 57187260
202 937472126
114 910391477
235 10258613
221 43570499
595 10403466
213 431709149
651 271002315
160 179096202
187 1000000000
551 212619334
491 231443524
594 207476173
771 14505547
296 51275528
266 81050087
563 98435893
778 67381093
121 345923776
553 3199005
515 102575809
208 101778619
89 132655862
167 32427788
738 174259212
405 1000000000
488 1000000000
676 4522947
113 8819893
602 177301046
742 131669298
384 82480814
559 4130150
94 6548534
596 58053975
347 31276276
380 744845823
609 191428041
593 1000000000
470 50251562
601 1000000000
771 709263572
701 69341888
272 1000000000
357 326896539
484 663206175
760 113979477
73 42184731
704 1000000000
69 46473113
547 107522952
289 288573756
682 210750934
229 112041365
317 245416117
345 46052651
195 365176766
37 1000000000
134 47795770
304 63749355
524 1000000000
195 176480646
30 23172577
742 241370121
356 67070894
33 41573984
326 121783939
28 337144301
427 1000000000
702 129069520
445 164925090
208 449247090
418 7076063
314 70659060
707 483471236
4 370623864
584 1000000000
598 76256730
88 170490621
791 256572628
605 134370665
369 227894610
701 57010955
682 270445204
257 977264546
715 258136342
657 1000000000
700 197529509
116 269184669
164 53252937
436 87757425
429 37581055
23 80909239
477 147418182
678 1000000000
157 57463510
169 40248934
533 241872256
40 1000000000
652 41766542
234 194137150
364 1634194
25 442189052
155 25693789
475 350016106
578 458635656
665 1000000000
553 20332016
603 963037375
55 350996005
552 59690958
726 29426306
714 422432228
332 1000000000
775 192426216
386 66591877
8 27174992
96 106154618
597 29524056
270 192054464
245 50379537
596 227512439
722 203495880
377 479367788
178 129819724
742 275540852
478 16037585
355 1000000000
62 219035970
408 206950200
634 174201201
493 234502636
665 1000000000
297 388697347
677 59222283
693 144303035
516 379775447
345 401384916
543 5880575
221 523485007
254 35516252
649 386981230
168 214695797
548 4984321
167 1844473
568 307205430
353 9324133
235 794028806
127 326946786
38 1000000000
681 464929852
465 210060511
486 369353887
563 80698720
512 464260544
566 2734456
189 189421805
512 23906922
742 55006341
442 176465963
387 124507160
172 125976319
572 102754200
701 111092333
88 32281571
215 97025280
609 5274216
352 406874364
573 156105388
673 100673037
21 281383295
34 1000000000
113 259495017
779 48649004
184 490793468
675 172694425
724 400519502
51 273291884
683 228151184
99 1000000000
230 1000000000
123 154171097
621 5870215
291 191605797
295 5768747
259 3729018
414 17853935
66 19156977
536 38697738
585 228030417
798 585989001
352 17599288
248 189167677
463 230178173
142 127296040
542 131878
167 46423742
468 253176097
269 13047453
314 1000000000
614 227557851
664 203447049
283 535158481
22 70965088
500 5561456
252 7783793
56 172373328
690 151043103
305 1000000000
223 220812917
293 95606732
684 13920085
733 106178010
321 402194764
769 149680923
198 96882699
760 159334170
194 1000000000
556 309478968
319 215092826
675 367323174
259 558812862
646 41409340
343 8090241
349 232572291
707 79085208
144 111342426
238 336956634
550 1000000000
258 19215067
393 766582791
709 1000000000
255 192684405
416 87361189
497 5163235
571 940695521
519 346524452
222 228907204
232 731959305
528 1984003
734 300209984
666 74104835
623 23030265
292 1000000000
484 136316462
502 161688323
709 10303732
536 1000000000
793 81568868
466 29635182
490 345719914
235 61781968
382 1000000000
652 225229164
670 3043216
381 712640987
466 11107434
230 92106205
290 315555589
79 132115175
373 373193815
95 79217377
149 173514139
287 109254700
584 272787761
727 30740051
535 25106070
143 15505117
650 1000000000
175 367124857
488 13121801
95 1000000000
219 1000000000
358 11703869
265 1910489
141 66776482
603 123831020
732 34778746
569 1000000000
731 261417085
42 63488590
593 190495492
440 25496897
744 233349690
585 87431110
454 713841146
166 1000000000
500 219859085
407 1000000000
154 52187243
324 1000000000
479 104793721
436 224918628
781 1000000000
273 4041125
138 346956751
417 352964941
223 28617342
269 6511692
20 199055281
669 64784524
625 73963194
152 319608522
221 1000000000
488 634233581
673 1000000000
755 281668239
197 35351413
514 1000000000
689 6573218
541 62977928
205 1000000000
11 1000000000
289 282496622
182 400967805
20 25686282
4 513035875
559 152929558
30 101660665
250 70124033
716 3040990
157 9239462
502 96808592
800 168741312
771 167918958
490 156546369
541 79519363
260 111324112
394 81658119
310 1000000000
83 318551814
616 100388555
128 151674433
610 34874095
120 137495333
300 232456415
421 506335476
173 489007674
429 232217669
78 91436769
409 388719905
247 103611183
305 2738609
80 52451359
124 329817863
384 514401971
708 19697092
241 18060618
495 503865589
649 81005806
390 456251297
593 52980072
209 36350758
465 953926487
760 211692866
592 289442792
418 366166003
152 278754457
121 58925575
655 26528253
259 330508325
606 155485047
585 453752874
301 1000000000
307 21595621
740 218663377
8 27788153
586 1000000000
82 58602697
200 221751037
727 555053977
678 32474359
384 318428195
76 423970562
725 65810439
610 1000000000
605 33498568
464 1000000000
2 249874716
477 113442391
362 473933797
722 1000000000
542 202858264
599 272041970
486 42908521
148 1000000000
714 3253309
49 166772441
273 113323668
21 21092178
517 275288681
649 355121378
332 1000000000
117 257566357
751 37877645
193 8216568
630 553787224
341 457045921
168 87912602
633 463413566
207 228908351
692 106997603
689 70274259
367 173050734
439 1000000000
18 200214871
489 757348
453 68693875
110 1000000000
399 894538193
48 216973062
730 285689996
21 29885184
588 58539331
646 57137603
718 130839494
715 820988631
584 192077245
396 121813415
225 22524737
208 342418226
355 429766808
353 78135108
628 162496138
325 219405037
381 18611462
709 152961841
198 176846649
681 1000000000
279 76632246
504 547518092
23 81057553
732 66026157
527 209818653
219 53645509
264 1000000000
734 243064170
743 6664503
365 379104633
567 6818324
48 918071008
31 26614104
430 58650171
614 70857754
368 114873126
277 1000000000
222 1260007
724 94824890
640 1000000000
459 10305422
766 256379965
450 385985981
480 152701313
736 149261772
653 1000000000
686 1000000000
622 474385471
437 147963046
11 346539359
442 325313
364 89895797
424 6136506
24 114736488
582 56186890
505 90242035
475 19417871
373 38452194
336 399213104
469 65378918
749 1000000000
769 69336623
474 311045945
481 290701
542 26118681
636 541606851
355 218819252
699 599515130
143 540114122
454 9962143
395 53334866
677 149722328
799 142352358
480 63861583
434 115801925
319 72089509
398 1000000000
393 428465769
633 485878306
263 121484596
732 29757809
545 7008423
479 248149044
255 824451340
74 11331285
552 98497701
708 1000000000
70 393575551
374 142578540
127 177863880
9 412227165
380 23047402
258 112466471
645 11416048
556 61178057
706 187890307
14 128297080
26 55926453
431 1000000000
278 66237733
504 283783619
286 9799562
305 33281832
218 192756512
226 149764379
50 443673585
595 15215361
174 117270207
523 393951667
597 1000000000
403 39245777
144 402855141
788 456131763
231 55840168
339 27674867
674 295344374
155 69364524
616 259279410
595 22053710
483 92957623
226 217850499
537 44980304
401 43532847
243 215088653
264 213961107
121 16783418
335 165037944
275 156099160
77 1000000000
584 5909154
620 950331791
769 365110602
370 295252011
230 237676240
200 60141141
159 678094
566 9020979
724 41290163
611 417712970
461 915800267
633 32042951
145 667689462
574 225121269
681 139320180
251 15098756
669 208806818
440 277614610
693 1000000000
381 475587127
88 205190939
17 206492371
624 910682715
605 460173
323 39728826
586 590625463
570 67416401
541 478809761
637 119308991
481 256288903
756 36127855
125 499266886
550 174032029
184 173051108
156 100443085
763 103272778
510 53864040
174 33141728
660 97277145
761 267357499
454 88212637
452 521051427
668 324110707
86 184614728
93 493539862
312 307277564
658 1000000000
339 42237922
67 271521161
524 66898572
504 306828487
782 319049135
408 91085958
384 363293540
621 523980347
777 418051562
765 573454506
626 656900533
337 15726043
419 1000000000
657 175483782
228 1000000000
5 34228160
28 62884932
660 36280114
405 264078253
359 203517510
597 1000000000
614 449168733
549 1000000000
441 1000000000
621 104866523
264 43816707
340 985980693
635 10881594
164 305050953
473 1000000000
3 237737195
715 36094311
346 351144921
697 238669618
465 339277106
491 1000000000
112 785251129
712 1000000000
222 686197585
570 109576133
548 184204979
519 437097067
203 715720819
312 35622549
600 1000000000
85 1000000000
150 146139728
710 4084668
428 93657064
402 245593814
257 45795025
706 48202448
286 174409316
478 316092817
139 846424
494 232694266
464 50973156
218 355871716
693 1000000000
202 1000000000
193 14825195
517 75511608
669 1914745
532 95026843
594 1000000000
575 1000000000
549 6764710
174 7831193
577 63482700
488 34845144
653 124687059
503 276941450
112 4197556
97 138401689
659 13559502
463 299939680
606 334170504
489 270592974
217 33325690
215 570425266
203 161242604
352 270282253
158 116074774
333 159649172
248 29129005
6 19549802
770 560913230
115 105318049
676 80115409
156 242047147
389 141939535
585 130108811
367 62103379
65 362050109
520 1000000000
141 123548244
793 1000000000
469 1000000000
714 157041782
161 85998580
451 191722279
472 220746413
363 96759257
420 6374290
491 526121634
363 14733408
12 248973407
150 56551112
404 213900831
589 712601955
651 1000000000
152 164459558
155 76490977
478 518159
330 12432165
72 250660865
673 12856228
94 151280432
232 39375200
584 80002114
615 32642155
142 6831783
230 11323094
56 47625444
492 388845126
781 1000000000
99 6853760
438 887973216
17 19569966
795 237285395
542 255398067
644 311078857
468 43681782
664 100283064
122 546335322
161 33763601
599 1000000000
37 11150944
660 7493277
653 62344579
153 126844697
1 47019034
46 292716070
649 139248261
762 310159363
108 199766152
391 97188812
371 674916373
411 30199991
6 21297356
287 172899379
109 169296090
603 1000000000
400 897022132
310 64631389
727 121531328
218 217870194
201 98196994
77 432846532
143 327679339
728 390755185
497 227688703
67 16039683
87 98638951
598 69308459
40 144342465
568 835760600
718 445641233
370 215719685
335 135858829
557 129819673
500 317743782
527 124756839
69 402523435
576 271477962
10 312345808
202 97298701
234 209505679
595 66410216
142 146531924
548 8182194
606 260648052
293 1000000000
578 1000000000
94 483847564
514 353481489
663 216818951
422 284625777
215 45361677
21 10378719
424 343208769
24 397450268
784 121492217
599 473571753
791 1000000000
506 1000000000
615 252038100
616 1000000000
327 1000000000
459 82846891
94 1000000000
361 158513471
85 478199886
11 35532933
372 470489096
25 27093194
451 840703980
27 846064937
489 747333287
344 133803158
368 929865917
377 215496884
510 2114730
742 380574146
220 381702890
711 411132837
466 22818745
708 270353238
135 45612913
261 29622238
165 168392417
49 61938771
690 1643551
721 1000000000
791 29246740
781 411254266
668 135176640
685 582445507
9 196619595
536 350806410
485 6660394
504 769898293
185 409364774
435 20713711
142 754876029
338 4557535
490 245622760
157 270591999
117 120731616
316 1000000000
729 984568
694 50060635
732 1000000000
756 43804331
615 226799325
798 38044435
770 350176379
284 5054226
213 80070416
22 55163385
264 72371185
340 83590495
482 248792764
509 774465125
365 1000000000
794 91976503
687 345376971
435 54013
144 156176988
304 35798401
282 215014528
376 439487190
308 70573430
629 265804
165 94109728
493 372262704
182 342964518
265 132687027
239 263979096
209 337512117
56 152608465
749 181685762
504 332466627
580 1000000000
569 217915647
383 64511222
513 1000000000
518 379977209
793 824699662
225 133226092
265 79275437
440 4664699
312 92649427
243 56209958
432 1000000000
505 259500848
23 455793816
563 797989862
54 342115365
777 133033234
53 500157649
547 301113091
348 176747703
648 101964072
178 206093956
706 96570936
64 1000000000
247 320689899
175 136473290
208 9615847
485 79598498
21 1000000000
106 94654970
462 1000000000
648 108890559
34 384610266
677 1000000000
26 66868147
746 33106066
734 69351803
639 72238690
374 103407044
300 214346506
42 183437095
441 279252126
66 16130694
301 72306197
165 201806748
306 672126885
28 65717629
46 284461147
591 291465099
73 45594404
102 977746305
493 90553597
712 79898605
385 6953235
191 1000000000
204 129264647
337 90015148
279 44230078
583 1202734
778 14284764
777 1000000000
205 34626964
159 2685313
327 97599484
528 48502172
66 42998683
549 53182778
4 127380343
742 120395295
502 186678142
539 75097635
768 189139468
716 742328722
425 25038040
513 1000000000
443 139163264
161 22982784
700 242949258
437 109612583
757 3441882
709 124338153
366 199973694
345 138764107
175 134783831
248 1000000000
191 250229578
108 280979434
168 114885498
59 74643583
624 1000000000
142 1000000000
576 329434483
621 1000000000
415 483917146
800 180730737
311 814115320
398 856048543
270 36181484
224 120580467
109 218058998
606 243658396
380 676936219
624 224000372
451 34953408
318 43277796
234 126436994
752 1000000000
184 408527013
621 156269800
23 253685624
126 73636247
45 1000000000
171 111757221
483 787828258
188 144310168
192 342307942
216 647060785
110 49074036
41 109136328
403 217113775
469 1000000000
696 1000000000
581 4511213
517 37907941
577 429526846
226 11157617
689 71977579
22 183131515
572 123900920
11 75855438
747 130174801
263 304382094
230 321738884
531 38909234
789 33192542
247 1000000000
224 107160245
186 7833133
175 421880059
710 381807233
617 739026594
257 307407751
599 316383320
628 84787742
129 216195663
327 1000000000
271 557490247
386 43399934
296 680111175
428 4327303
342 1000000000
751 447923844
511 45550534
177 680420
556 790350865
187 257422744
69 345140373
468 701911598
82 268889511
710 136810940
122 136631004
535 334875364
38 77764570
560 157867552
382 7622462
281 57897916
10 902186874
506 1000000000
594 134887540
699 1000000000
30 131582513
579 121333697
661 367412531
92 92393461
480 1000000000
556 11816155
711 63312276
476 59310639
18 1211225
19 410052443
520 163791787
475 517267170
723 75027034
250 283237274
505 586035362
601 244092084
35 196431970
384 93047686
665 2595118
247 1000000000
67 16006505
293 98041852
584 200711512
244 409392375
721 150354975
458 251451368
326 18591284
336 10996077
15 518207541
686 88824228
532 61411032
363 986553380
93 897411400
337 385291269
401 528972891
678 53059898
313 243049558
435 640384230
317 39080431
736 205994459
389 190497950
213 118458358
664 9477830
505 74055137
288 1000000000
278 195352381
483 101051576
178 318819966
554 184718240
374 187513695
413 391642208
233 60687100
548 56524144
373 1000000000
742 32108921
512 26877703
492 1000000000
211 343376704
127 70527313
374 31616715
484 6031781
49 329694745
454 398248140
44 74388622
556 702055033
590 62218954
797 15479268
1 429848456
386 234149663
171 811019176
643 688332273
437 47676492
168 14054015
358 564562606
441 147820262
104 322201161
541 411040495
129 103921570
477 114959405
666 1000000000
481 3466061
411 69674596
81 1000000000
140 1000000000
181 1574637
660 96829074
276 147074822
509 131294951
87 366251217
45 150996707
39 285468620
557 188569918
169 1000000000
101 77998388
520 6608639
412 55766993
619 168032112
380 103049195
537 1000000000
555 1000000000
699 277219323
274 124439871
57 105442981
665 74625769
155 114655685
712 1000000000
777 178850491
70 275443260
74 2890088
445 16407095
487 1000000000
371 388802144
616 587979747
657 952049
565 576402522
62 56258481
54 126823564
612 737163525
82 304056321
681 777897499
18 1000000000
246 45995091
63 87444093
403 460274886
510 436292375
136 255317975
506 287529638
189 212355120
602 79004006
537 198296280
613 117181092
134 1000000000
132 479371
138 387374818
63 105611055
718 183686275
158 160463391
249 399030466
745 105065066
597 58698819
167 762639424
72 5839515
513 103890876
251 187508059
703 54505863
214 159978785
233 1000000000
353 1000000000
295 49071823
291 91054992
384 262201325
646 167914855
509 274653597
560 8435108
679 454619533
330 57507916
291 31743946
508 418621147
796 140551298
269 55761932
249 0
7 42053271
353 115607561
144 45628581
413 56502790
689 6400181
21 477726664
498 159138129
241 157793591
443 101420258
25 121579789
19 203658764
276 25461802
740 1359874
555 487709470
20 1000000000
678 437579400
460 1000000000
525 1000000000
499 237756337
584 309125473
147 404737356
606 12631091
274 42091253
216 105025885
186 75060130
287 535888443
17 505821498
472 322351790
735 1000000000
174 61549114
366 486165525
488 356162
420 199521525
205 364265185
715 45275222
262 128563592
553 112458855
667 302740159
679 83253539
84 415515102
524 467816239
409 1000000000
226 307909990
593 150916388
719 110135761
517 157768635
156 305342460
317 416263925
369 75931983
673 38516465
86 42969967
473 358134186
466 87994520
332 101849894
207 230735355
643 12534607
83 107761310
327 42981608
423 27964673
29 247410403
403 191832590
240 352856598
638 5370938
71 586370521
786 155247836
553 225577205
85 341259957
95 203421984
208 739657035
145 46991226
203 1000000000
359 160418150
430 524816231
105 437112849
672 143361995
542 706667802
299 504220607
623 884754560
309 70550534
580 57351161
615 164527315
773 11543730
648 338584054
26 100361755
354 340891870
234 698793894
219 487984744
382 313409520
61 1000000000
223 8645495
622 21115545
722 1066419
566 4418956
450 56838179
479 4241047
342 112202967
623 820312701
469 581588869
16 676780434
552 164617033
744 155621579
439 16273122
736 190666135
394 54970593
767 354455438
681 261994658
143 257439195
251 143095303
374 11351758
9 22789821
29 69276495
91 91968918
652 235719460
345 41401525
747 228537019
139 1000000000
449 10672431
24 141511563
376 269002582
137 436789534
22 189879027
551 292173896
292 62931919
215 173297832
682 105060576
196 144613671
335 62433846
341 119659560
253 59561960
721 354628662
474 74791565
641 557448712
623 1000000000
589 1000000000
164 366596089
669 59415533
1 1000000000
537 190966241
589 66200204
8 951171432
338 117840350
531 620345587
438 25414133
770 179113057
706 41106489
477 36241335
189 234838343
588 116266462
497 1000000000
470 140509430
740 60339057
676 23674441
448 595636
511 205506612
363 59724901
332 423885602
781 1120301
630 1000000000
464 7910560
644 231967728
442 764043506
541 31100242
693 131792699
106 676939951
359 157253639
659 162540998
377 120663212
64 1000000000
82 105936108
409 1000000000
156 672556089
229 731756576
733 200932821
749 19036157
702 1000000000
697 470484943
487 55730932
561 560953464
224 203545062
253 56025668
624 60768281
548 34195409
385 66141900
623 792416177
217 80045740
391 175629449
129 72166948
465 1000000000
705 88137583
248 77926836
128 52241256
739 1000000000
776 422212247
89 3855496
479 1000000000
259 125373
654 7092045
681 261029768
157 70800806
627 267552246
436 187970527
777 34362371
762 1000000000
658 136837613
121 17541358
695 163378039
55 1000000000
640 94511379
733 1000000000
693 1000000000
434 394336815
670 401013608
352 76404254
322 565907
45 151598270
394 272225759
387 532073117
63 139399020
488 1000000000
774 81425989
676 1000000000
202 1000000000
737 202354844
18 52967590
229 380297229
549 104959416
58 21639251
748 258316439
518 150924276
367 95572158
274 1000000000
470 72466570
645 48926316
553 27275593
329 762912010
15 384301582
516 117464102
145 71868646
799 45582637
183 26134356
162 446614973
105 405459036
373 1000000000
559 90914408
608 153218150
656 639383522
10 190275093
181 2736110
444 971918552
231 280011316
318 44320668
555 65798522
664 1000000000
716 1000000000
594 92438946
593 125613522
371 1000000000
641 88915173
164 24206276
389 329031987
333 339721
741 187391981
630 750881717
745 487461011
743 49466246
249 82924825
327 1735524
636 68659786
224 104918005
539 53944633
280 25875575
126 88105392
312 131520611
653 861656622
743 1000000000
16 148659427
463 262449097
622 177414591
758 469948456
721 488949849
742 165852384
351 974225601
613 121200112
705 360752917
251 10013698
382 156228321
786 1000000000
96 258931186
720 515988352
301 1000000000
671 668134088
238 194931198
101 657045372
747 85048760
299 433485851
780 296352722
280 1000000000
409 115678337
662 1000000000
761 234950206
619 57698247
181 62998538
512 89953146
85 25051872
733 401824735
609 48225345
426 99197451
97 595507086
655 152467605
764 206751607
755 4269311
348 158067871
511 1000000000
71 366156426
347 110124468
326 34007202
591 1000000000
320 457573616
323 144716402
191 20494270
702 104632107
489 1000000000
745 191110893
647 14419772
460 1154297
65 879870840
495 1000000000
255 189418075
506 376107450
361 259647785
340 329044350
678 381034671
199 142835579
287 71176799
793 477334388
316 7789019
211 1000000000
709 1488990
604 199342745
450 171582477
606 57225509
666 77279951
639 297574553
247 258370827
297 446283198
543 123776234
34 89372080
315 31142828
210 33684206
338 307562147
35 257792733
238 10902505
635 259965153
21 1000000000
164 124705378
688 197367899
68 132496430
295 545404250
100 369425206
34 228083652
587 383780554
489 163545727
579 9938208
419 533245564
146 21423818
89 235908676
353 38758076
595 124249089
56 152940341
537 1569464
447 263888974
755 26565896
574 103792175
616 479954463
92 37698371
162 922117079
66 102466425
167 438538076
24 196027629
352 145003160
550 556934233
436 26853585
116 991640734
109 449229040
9 139718299
17 120826469
750 1000000000
777 135422605
619 56366757
61 1742614
456 19500077
341 69436167
429 376679373
185 197304629
225 1000000000
208 377790705
750 140542747
227 134091315
794 264062190
666 53713289
718 182301321
413 205604355
593 1000000000
500 1000000000
173 140052779
6 303488926
520 23862924
93 220166777
428 15381441
127 550081497
319 76725338
85 51146519
649 32419616
646 32722182
276 93898934
572 193230106
614 114707790
509 75157806
649 1000000000
306 283830655
195 194397132
579 10241525
221 173002204
408 588752269
638 258365854
153 128939304
144 202137570
589 1000000000
441 119209084
93 4064100
514 455517258
337 281090738
563 11673072
241 311138809
116 59185567
709 49127749
525 66441471
692 204173009
581 72211741
680 204159820
613 172055904
455 20001039
501 122485698
218 680594059
765 93258088
648 90615849
517 105620821
667 11687278
500 1000000000
89 391189572
691 669056003
587 254989748
554 200744246
25 546688369
257 50944527
619 282106
64 304433289
745 49686928
334 15527240
794 244950879
501 631387340
263 213251233
187 359922283
696 107869354
425 57606286
533 19438883
390 312042961
774 481223082
60 1000000000
690 52073021
689 2171308
323 360056082
111 818269468
543 80548259
60 543108552
719 1000000000
32 115077693
154 1000000000
613 406242837
138 542961588
433 180778386
421 187284023
238 175793728
308 1000000000
290 1000000000
63 24179957
662 317057221
654 1000000000
561 13957729
169 15691964
189 33977995
215 128606012
416 452064505
225 279743122
195 2038002
239 349786524
654 1000000000
393 929739361
681 1000000000
631 164214284
60 855367684
736 107636294
622 296322810
302 259827109
40 229270382
647 126508364
50 279051458
692 231688172
596 226055403
156 215452665
790 314964388
681 10610036
223 146998534
1 1000000000
184 1000000000
45 71986630
457 75471770
213 143054915
314 5471540
257 99211455
691 741259462
505 42944838
315 28269677
356 50035291
348 884274436
427 498148793
28 726088732
182 79227651
580 282512637
141 49279925
764 1000000000
280 13225315
779 332051923
382 43218597
314 6311143
137 626830059
754 113102229
127 406685540
121 401945351
41 40452735
759 18423350
590 39313583
630 397724758
24 218771777
637 434124607
269 430879448
691 124099181
438 547943744
33 952957995
91 1000000000
335 83148436
484 156673479
260 429110366
89 500751472
458 274871427
257 33417932
487 266123849
677 200756948
708 8215530
205 74136039
681 113440961
609 29003143
382 19470246
41 16553096
715 25860260
460 42609695
727 121808860
116 235907905
619 60095047
103 1000000000
143 35239676
622 203907602
427 6762100
208 56639303
263 169418174
471 1000000000
362 218424293
41 76667277
285 1000000000
495 9060873
520 428485600
17 223089571
83 1000000000
503 990464744
6 140205230
521 319468691
264 372675626
366 169209855
67 125388767
303 366998394
221 291299993
532 1000000000
287 98257993
741 616367905
337 194612958
714 13579870
282 46419096
714 19744658
355 188931252
751 292691312
309 382043746
127 331294354
502 9589542
355 1204412
142 165249610
674 14396631
295 45274204
486 217115686
712 126858264
309 153178451
728 706427451
504 4724269
672 7882268
279 413526442
424 292744121
570 222345680
183 255425223
329 339493790
631 128006533
299 53717697
526 52549811
681 28561572
133 228178565
299 65086303
4 107338996
505 996004621
563 731868
795 125927972
570 978795790
472 305840737
384 1884912
666 289509175
110 24649664
743 157384100
236 29342397
744 150602124
130 118962496
388 346101302
632 45707209
357 110814018
213 38223345
721 191167440
610 103980245
177 395630889
231 251763080
13 9518188
588 16613837
77 314493257
601 45348891
601 994338759
757 203898515
56 851501101
202 33743004
435 328205521
190 154192038
594 196156074
538 12927014
797 177310000
38 1000000000
732 250888147
713 166168562
214 162803867
428 1000000000
757 9352705
344 362383382
95 545478222
755 62426094
477 44490066
165 92486654
182 1000000000
312 23075770
180 236811739
83 503510387
573 97468308
221 38017133
282 13084322
735 1000000000
147 232567835
225 1000000000
336 61561669
650 202600478
57 348402537
708 115170027
373 78309884
597 265350578
45 278458986
582 1000000000
105 167674875
255 639300254
17 137050505
680 119298861
269 35491303
489 88540674
452 326513033
9 167149199
288 10317860
273 188755112
199 71828295
297 149387500
770 442936150
249 74769341
696 333705
585 224279047
467 98430460
512 187187144
25 59725951
455 1000000000
627 188035503
38 560505965
681 350888760
37 168069903
643 202634095
12 385791395
585 137778866
354 489182158
770 171208393
465 504971208
503 560932935
127 68320795
272 255677460
53 609014242
309 84909784
571 116884331
526 8544143
536 44105600
2 297928247
213 68804558
251 119045768
635 203764904
223 167496413
208 189848487
343 350607731
92 109789751
522 182086794
201 200802151
290 86744970
350 79400507
677 253564704
194 245443262
92 13209652
94 146475562
719 10233715
762 98024093
678 336261648
381 72406664
233 53258201
497 54654640
319 264210538
316 487453465
17 17998798
455 612014994
167 220717985
26 307306410
585 1000000000
349 35424781
383 438315210
120 5941754
528 38803687
434 41340140
230 31868217
436 59041
551 266216761
710 535661743
412 301910792
496 42066845
556 1000000000
346 193735819
385 53420741
651 337395813
257 73385941
492 23052726
149 350785774
581 795870520
389 946785983
446 415763054
441 454913923
479 361103965
217 604433242
47 222530728
460 38862498
120 4114898
379 47648529
128 263098367
110 777305259
720 659229622
77 265563849
464 276031313
32 198183702
327 60452021
142 46500979
447 90579611
385 425156286
798 967078322
383 377299052
77 161967055
369 629098799
532 4600347
702 21247644
602 814801160
80 648795866
201 271013276
77 74030215
583 6729955
734 254045298
701 8114528
107 57299143
115 420812101
284 16392436
624 1000000000
185 1000000000
414 198153081
745 244816012
131 274597911
53 1000000000
648 516232217
293 4027696
693 15664435
193 79595344
498 223692801
145 920878997
583 22116413
476 272487241
347 5933666
204 274043605
727 1000000000
167 18779605
227 85427697
278 1000000000
135 1000000000
640 373184421
683 777642304
335 541100704
790 30173162
425 33570924
369 25286918
791 67155876
4 128106668
257 343458231
119 439512375
719 27168647
338 136408259
297 653387820
668 113460543
54 62949171
799 815617559
415 114627625
385 229353341
396 188370959
363 551820534
165 34342603
453 311848553
434 5345249
694 381594297
346 17634046
136 75085423
327 37073619
161 204173292
31 1000000000
394 51545680
331 26443978
331 115718864
50 89855464
747 174848687
734 73259631
84 159789852
149 136270034
428 15177629
192 401798281
284 1000000000
487 40991213
684 17687801
786 1000000000
483 2775939
73 351796192
267 137031130
787 301640635
778 108220474
121 1000000000
617 1000000000
227 519705541
432 838449263
185 495238927
199 133560780
67 34423863
54 640622843
648 10944353
580 14489140
210 665470528
378 389287816
199 26512129
256 6021591
80 275125012
798 210817225
308 434839526
668 14506832
573 342889759
449 475145248
49 3181737
566 38512881
473 10317480
387 516913
445 6848990
432 43630013
613 203460963
741 7762327
569 105748282
73 63115665
480 25721244
326 52655804
451 4630835
290 74588999
170 50001798
646 39910338
29 2694444
506 87091270
4 163452444
261 343274113
70 379320103
785 272801813
685 598799345
612 88068191
287 31207383
263 562881920
709 4727823
162 499752959
294 252131045
668 44844419
428 330294852
671 226368739
381 1000000000
17 172554998
162 28287060
763 302582181
67 1000000000
357 39605943
552 587219343
310 548476244
569 371359847
440 1000000000
221 312253694
401 424658229
221 235940426
170 159550223
321 112291381
491 113680067
657 107668488
220 98228607
757 102135502
709 22962253
628 19820506
365 217147906
152 178712026
733 35745786
711 67805308
125 450481823
202 1000000000
309 6214601
616 391357019
397 279705717
651 112742866
108 1000000000
569 158461311
795 101613732
219 72309126
738 347328938
473 288978265
457 1000000000
443 125652361
600 24172103
41 499573859
758 10920865
618 36054273
525 736358695
743 148683217
419 78185242
8 925829053
161 101808512
757 463159643
111 242022690
86 192486011
468 220335398
18 108283864
346 44461296
115 138104108
455 489457782
159 12597071
356 94622665
767 481109900
377 57239282
250 492193358
365 304120990
762 50564536
234 443915004
293 207714027
182 118772048
132 681137391
154 122833072
159 121509141
30 81650843
542 182466339
233 146586279
41 358927577
709 251540546
231 77083968
120 121645395
1 1000000000
363 114509659
383 52396258
742 343439559
585 1000000000
81 74086426
7 1000000000
116 439151897
544 265648671
54 4831011
126 57806821
384 86299147
71 160854513
58 487176718
452 46594373
172 846994187
604 11668660
798 580771345
793 260168714
247 262167527
65 123457794
640 900818728
61 260574627
385 467544598
373 35323069
642 1000000000
49 1000000000
619 4855343
377 148067764
484 13348222
596 95123035
244 49706582
587 210861176
356 232215764
710 195791790
764 421180493
525 187882953
740 85060840
424 249491257
323 476942529
190 92636770
131 89938540
89 106789172
106 486195948
511 311395289
289 171655676
153 19947602
784 1000000000
206 31453466
446 701927937
552 26338222
277 1000000000
525 430104683
379 69413870
166 29335011
345 1000000000
635 1000000000
599 306843869
116 1000000000
61 206531457
281 1000000000
242 21753946
721 181941190
447 15033310
197 93249269
300 1000000000
445 19847187
481 16208330
353 19604864
230 191535379
281 241098068
131 402964145
460 162158218
415 561601091
292 19897591
355 24096978
231 385202659
311 159533589
734 49660009
3 515708298
80 75018575
143 127213799
263 1000000000
226 11016306
329 59672805
133 108749016
287 4457854
544 434088308
497 238607066
91 261490169
743 50190071
350 201332793
73 80147933
113 438056703
222 79751994
187 148420380
15 1000000000
229 3202644
164 10267442
471 39340213
709 51858920
313 1000000000
346 67198848
306 687474565
746 82954616
556 258331612
31 66738204
461 60977699
351 414981007
606 378472146
307 1000000000
391 31223200
34 423780761
335 1000000000
470 175037680
96 73482176
309 4744324
544 92430386
456 198843047
568 29689910
151 13957964
16 7500340
202 59873761
112 575945626
393 266517474
639 19389753
667 5484798
582 146740598
73 54712273
621 231851046
795 530092159
732 191284238
377 260565881
635 222270258
651 412545222
722 25159894
408 880976939
264 106444302
234 305729934
582 43264965
327 309683882
500 211011830
56 91839424
730 3246832
484 144287330
96 66044432
501 682827967
77 1000000000
113 90555380
10 444940097
1 1000000000
543 229268860
461 397734769
724 40356547
29 8228226
401 244582928
505 99644149
766 226958776
8 194688142
130 903326792
51 861713138
710 193847430
130 1097789
146 94793591
701 79635988
462 11149593
780 87892819
289 830703117
630 719585350
245 210787
229 74314110
624 138208984
639 21820355
379 782220636
45 314029719
766 65271234
342 77410257
192 584168584
260 124226125
619 46224112
381 10588596
741 117931836
234 500668332
503 328831868
691 1000000000
297 35389112
160 48979216
3 76558194
281 315043062
748 1000000000
549 17725687
77 61638242
589 159173499
78 227843447
377 371306625
279 83602484
465 80113714
16 1000000000
701 526201693
1 329456441
36 47383645
721 124269625
176 10722321
553 1000000000
199 87828955
241 31671882
114 70334402
657 150178125
280 393861444
209 378315555
707 6149135
376 560387462
793 168543575
367 207937509
67 40478688
702 35531586
265 57104240
269 1000000000
563 1000000000
164 10900689
585 1000000000
587 382662747
338 142157247
745 49354965
599 231321907
455 135645974
160 169400815
141 26244393
21 393778669
483 303380264
94 14271569
656 697027267
738 87551446
190 239169547
331 341077856
467 997355952
671 33973945
632 108288055
519 287098900
789 339335643
266 395530168
305 12473814
50 306784777
438 234862919
165 55875843
522 115472440
620 1000000000
662 272853015
175 11725862
354 389817298
662 232018342
342 36659474
425 3978227
761 18699856
719 65110324
212 148070354
305 64776170
143 1000000000
791 6039231
530 2527249
457 258845398
741 48707461
207 133710736
752 17410872
112 568817273
346 295014878
470 241067435
140 1000000000
263 328347728
206 261420081
44 179683578
456 122554321
460 162238873
162 156302973
113 131647894
323 150858200
577 366147023
372 539684324
677 259695683
638 47381170
325 75705698
486 209522949
393 759541033
791 35209395
569 777466076
632 153496097
348 885724934
496 143994644
603 56629025
584 41213100
638 426248785
488 229091329
749 52545894
24 1000000000
272 563044743
703 274610700
430 325695237
679 442320016
657 263380988
406 694530568
703 188866386
533 180039042
417 710006478
108 92284367
702 426751480
98 241372074
192 39533384
257 26363030
461 1000000000
463 1000000000
655 179658158
597 20845606
715 127344684
507 2611437
780 30357662
137 72105460
25 1000000000
486 2831590
697 59271399
571 96189264
661 1000000000
241 163554356
22 142954656
77 1000000000
161 153040756
666 774361458
705 1000000000
223 132619199
796 31062826
451 291081896
540 59447217
527 342230590
679 420908962
779 196653289
390 1000000000
671 1000000000
96 45117771
51 32767972
703 669713034
718 238303105
745 8760040
633 203908467
168 35997716
445 296451828
65 135612783
703 234085524
479 347814522
138 96226198
553 3451461
5 68272254
614 4126157
55 1000000000
767 131421143
41 233806339
637 683948613
707 1000000000
325 162098597
109 105137084
610 162096010
206 42620081
698 227101894
112 136758442
727 1000000000
793 0
511 1000000000
50 147281965
539 69566458
259 915532118
114 92624384
531 19807762
46 189813324
748 281124797
629 83355127
404 255972438
337 241491571
404 7979474
359 228320530
84 152803724
706 89050164
732 96946673
265 17141815
19 732727979
707 68276045
322 226328397
697 432144937
754 677888223
564 364174775
40 84567498
601 302312058
47 1000000000
307 184335873
686 150494997
264 845181582
716 831981329
770 272459883
786 288238005
103 21968071
72 1000000000
352 1000000000
534 1000000000
564 1000000000
324 250285723
621 9989607
473 395742118
177 709082366
414 34918177
618 328490770
348 1000000000
669 342532213
792 713557303
725 108978896
221 291961102
121 4932817
210 297413971
16 19166770
734 339316372
483 16149971
170 238705599
571 227120277
190 581799013
605 49995817
674 1000000000
404 344774139
93 213494312
103 143081417
121 120394987
157 182608024
572 63937536
735 1000000000
271 592302657
85 62207862
186 1000000000
167 49495041
4 94952610
28 236787013
87 310572584
61 114954931
473 544844037
371 669430529
275 3019996
612 1000000000
109 413657833
568 148786650
399 1000000000
57 47119223
544 331542537
749 91909051
425 209528363
606 116588043
627 312745273
306 1000000000
195 317168185
785 73337172
740 72586026
517 343599916
381 105079764
53 362910387
213 471065915
392 403708951
565 290180394
743 37489539
549 64015639
666 3068003
77 35508164
521 215300324
341 163570814
475 36344651
740 134335717
121 216629244
131 1000000000
76 1000000000
283 59373438
538 539464069
177 110813304
619 86387189
144 14601389
393 7643633
671 40185251
538 1000000000
101 18415988
424 192525640
619 166836778
761 255364355
697 1000000000
757 48292448
631 69552202
454 720231647
300 683363361
371 15466776
546 19048952
515 29526048
31 28928858
287 76512729
236 97945039
495 21908224
81 72171618
347 1000000000
789 225930452
778 964084856
194 54407589
5 492739171
30 106882172
149 28441220
786 523252263
64 1000000000
326 123796894
110 1000000000
322 47303322
777 138646747
109 207995475
311 65295476
496 614358708
578 42278403
436 1000000000
528 1000000000
30 182623780
169 118916266
185 239385510
567 5386529
748 80696709
129 188245758
126 121326836
654 407030011
312 339861322
487 322964474
130 409586154
596 171377419
356 1000000000
93 126848054
294 298434156
73 335280647
431 6132854
609 4878811
9 3031430
270 1000000000
794 16717665
470 11237786
330 278190730
33 82181820
675 127581389
537 1000000000
556 170876979
452 695636992
332 104848695
524 12459972
268 620758558
727 466864981
436 56785319
621 455104536
396 190919951
344 417956562
763 384695609
223 63482745
747 54483965
585 38821543
706 4710095
511 152442547
777 253064484
361 318613956
136 394354138
495 46059684
358 353414116
312 55008960
77 419238301
333 112950826
419 1000000000
535 210482561
657 134401004
508 588176138
671 1000000000
196 970668394
597 28842040
537 105679482
122 1000000000
193 165097785
215 98722948
710 231308719
245 1000000000
110 43672794
314 388752255
513 1000000000
750 300536725
777 181963798
91 169907353
173 248715757
711 336659747
788 52773964
91 95780639
103 35316871
351 93551851
462 117884200
571 109618525
433 311400973
535 534834632
535 23857178
346 49721650
297 58204288
110 160176847
272 99740542
473 119676706
690 719238524
35 183735637
183 214835011
726 532255
681 36866756
281 1000000000
430 439743037
627 313232499
720 35573125
365 263402531
85 6208313
15 9973944
613 83694778
609 29819669
42 197769167
266 849969665
779 347096526
148 526829401
175 1000000000
773 120910928
351 397070981
710 999758639
675 1000000000
415 220213712
355 58976729
599 292913081
102 241961251
504 69855854
725 40089697
776 46555653
153 1000000000
144 298472093
632 439940235
664 1000000000
410 139364700
424 101778306
169 117445279
71 2104716
523 38847045
734 270355185
522 240556155
406 128720239
12 4075748
789 128808841
313 185990749
259 83984353
539 6020709
330 4912510
761 49766
240 226703381
538 1000000000
638 112958873
263 221294409
220 1000000000
328 44402401
754 392921945
325 260378213
520 278932724
229 355256027
581 1000000000
721 13532475
403 42435187
530 508696432
184 221259336
462 76451319
60 657454139
45 26601304
41 197027431
313 248520881
486 711606329
504 84602778
442 1000000000
564 161376763
782 38428675
211 161050948
714 314409496
125 191684468
150 76337239
60 55944010
217 1000000000
55 113524589
381 346265268
757 51179289
296 6331457
95 298820892
291 250218864
381 237953660
150 70327116
471 29772380
8 296966513
404 164406886
707 367625444
221 211747273
781 342704122
283 1000000000
783 205880641
52 71937681
305 262191886
656 319498591
443 105413141
729 381780546
404 167757391
629 24341127
581 119326598
462 386466318
183 289648703
362 35951722
720 172495439
785 7593861
312 381958
365 16289041
633 23666863
741 26439423
249 164024944
320 666655115
609 364982397
519 63274270
313 133730371
162 1000000000
105 1000000000
793 1000000000
441 929532364
243 169719423
688 94704420
25 86178424
440 576502516
84 456663238
439 80156550
490 1000000000
85 13021958
355 714396197
92 896247845
9 196050552
755 32300306
578 166615556
609 233171650
664 10719088
495 267279458
177 2110093
645 165987858
597 151574058
395 1000000000
270 1000000000
424 218142259
611 77970478
678 113713838
411 18509042
171 377973833
479 1000000000
320 272209795
151 14111534
653 79269939
43 266199456
217 261347876
546 66082671
78 596056242
101 305793841
786 284303858
157 67098792
270 461392763
560 1000000000
362 24536136
38 45062271
686 1000000000
73 30916567
513 413203777
95 296914382
268 207762501
626 51519117
184 261163920
328 251176749
171 72216593
73 160867942
525 91604108
223 277631715
648 320255407
593 143949354
642 1000000000
486 398737101
356 89492675
455 200838508
54 227794334
380 10647712
800 280483203
141 1050179
234 110076092
1 98065786
187 64256202
705 482753369
253 178605135
438 1000000000
662 56068609
326 45047106
495 81671591
761 125637937
335 81045005
377 54363413
480 3222690
12 87871816
40 878087786
636 192060663
656 246629674
591 1000000000
416 1000000000
397 10208099
32 1925727
320 133478977
471 82802805
271 26320034
47 1000000000
641 219415159
686 370788439
799 64758266
573 20379679
113 299567636
324 80895528
351 143685012
586 635021368
464 270831016
505 366531434
45 564901883
727 0
319 253450776
333 375995836
396 1000000000
323 271827202
284 1000000000
1 1000000000
633 204478830
142 121908055
425 139818031
404 244855059
54 488156580
249 61028243
38 120624977
262 44847816
225 83897146
674 89110482
529 271036492
23 157791896
93 69451543
299 200830319
44 15847989
583 42255081
327 428627917
595 199401797
278 247019324
23 921823
737 324581452
795 62804876
527 7060715
518 196289136
457 353680378
162 124911591
632 1000000000
117 56448521
194 203313725
648 272569182
175 317494105
194 1000000000
265 65065075
525 41893622
662 143123410
79 22918334
576 72135282
241 64181088
621 160601168
635 91194039
581 187928720
53 412351481
594 212231248
486 218968399
539 193783329
632 154510264
391 454280131
369 47869514
767 191851222
794 1000000000
331 421791831
763 110526527
371 208099561
475 161078146
62 1631220
420 56524006
629 299964439
316 28511971
353 1000000000
684 96977405
552 65839874
28 215962266
338 403461488
436 251508122
169 57169999
731 53638397
211 427009392
155 517056421
698 369981432
26 901684329
100 90913042
129 49591716
217 86185451
151 362276638
483 17466440
742 243595452
73 467314704
244 328763282
754 21283778
202 69076545
359 175996463
80 109994245
304 54719689
46 290906488
181 1000000000
684 146688
381 41574298
689 1000000000
113 345881147
7 61142633
282 124350530
52 149954568
798 282796033
545 221667863
389 2219733
725 11497692
313 1000000000
506 3190213
192 318384437
726 1000000000
676 87792807
690 280518099
43 35216372
278 38377437
253 1921289
138 13523528
516 1000000000
309 9074817
775 73497307
33 1466393
173 186615177
532 109203982
799 437015095
439 70342302
485 36863565
178 341043384
679 33048166
12 6444096
460 6264441
655 45897815
190 150827947
769 194252210
675 90874043
619 74009
132 62446239
21 582639563
680 5494483
295 1000000000
569 672103295
424 440236800
317 260981499
418 619788249
158 45507435
411 752250588
450 163234509
92 97637817
466 94438770
428 88205680
661 164503577
405 38760207
117 61441313
189 181847269
344 113013959
77 129581640
775 20122517
781 85508128
298 1000000000
485 0
393 12183973
221 13516662
171 1000000000
380 250879917
346 1000000000
44 58826072
796 123436559
179 96669017
218 161349635
282 71654885
91 53002342
488 45117627
745 49326425
551 359486
10 49004164
509 367323883
552 228724251
19 372475060
457 345680486
785 94419945
662 213138959
703 167944474
342 329379165
324 611338597
339 821415326
42 64856560
723 169002373
535 145933263
671 281710916
404 166778416
319 257337239
393 4005925
155 159578124
285 765464661
154 165585336
474 245559737
230 83171694
422 746603794
5 404653755
74 6667845
672 4989593
78 85803886
574 240659406
346 61248426
713 167054792
373 70020455
743 83353783
457 340663018
66 13789284
28 369288775
608 163386234
183 113041119
10 24481554
321 51785941
711 845630660
324 1658530
257 108305276
102 2003449
158 271789354
433 227865481
103 1000000000
459 738860080
708 157341426
444 1000000000
61 116676804
174 169244538
153 202114799
167 297678848
450 13250260
241 10603156
30 349815111
370 179206564
438 1000000000
435 40780906
657 773040402
667 115867350
633 78033828
404 60882999
532 51839221
356 82559108
300 141576939
20 279847460
39 539985251
300 274446895
174 53500777
276 82498468
488 51730073
211 88724066
543 154597760
595 1000000000
505 284186300
186 232272886
255 44460540
273 69565150
537 1000000000
576 100801655
79 226497675
430 140322428
264 470103038
677 480513405
238 62986267
363 33993638
359 690205800
713 432827360
732 202876827
615 70073879
724 17562257
77 141414793
441 140393114
770 197729877
337 420571937
752 7985868
646 336230044
701 99261
670 615783133
530 296638296
258 1000000000
790 39681581
249 203891131
83 180740523
13 254129864
175 1000000000
68 398278782
244 15605832
647 424205267
584 41765773
414 282039700
83 46491606
81 1000000000
223 1000000000
135 22231554
498 353601382
458 191861083
86 212049145
672 885362989
401 222105738
178 316800539
460 111692187
679 639679338
686 52183100
585 146807605
737 712059733
670 426060339
747 12470075
16 332599415
789 854763619
549 16092081
103 18941464
230 1000000000
681 43479763
410 60127766
610 76108722
683 150376362
668 46518337
415 81316322
733 91847393
95 547696969
302 242621099
147 396250638
535 152736314
163 31611000
735 1000000000
630 17666230
112 129171320
182 2640101
496 808032000
585 269472952
680 172510234
280 259361870
160 532970211
394 273021946
256 93456846
425 24912731
783 63914298
315 85254681
759 9914454
682 73996540
126 56154315
252 247441076
493 1000000000
410 92929685
171 16267523
11 830652852
66 213334035
729 251745703
56 717847052
42 986346
279 165061598
423 692052233
709 59468350
88 184456347
458 177823389
325 76390401
528 589570499
149 35066342
477 15936560
434 1000000000
347 512904285
162 28411411
208 680713988
174 337336482
165 117463180
541 500782473
609 266340246
793 380162
334 287512
488 234926732
434 117018917
276 15983985
310 269830721
643 168393876
130 785889959
158 659155680
350 445007807
492 184198956
369 349694245
311 89293053
741 12834832
5 58374670
736 27537029
319 491611792
395 626913867
461 1907361
622 21608411
631 4877374
176 38375087
484 576009270
187 941044506
574 82281991
725 290031221
267 143346768
679 277949832
596 157234804
697 215742185
96 56340435
467 24578396
89 402297962
348 14252075
325 60659941
446 19827521
718 23945626
671 203594355
410 20461266
72 148055082
50 235285181
512 6284935
445 29034795
145 314060550
5 34790747
161 7067269
400 184915943
762 590485002
103 214670004
578 571843838
274 130297978
33 107595540
569 283397538
417 415434649
387 13260397
520 289883567
538 1000000000
128 5158137
4 93590012
751 169803724
298 130362053
446 8117660
307 1000000000
180 1000000000
233 102058112
795 90573036
530 262276344
57 321261694
472 109833306
55 10212065
545 273690206
605 1000000000
630 259154933
243 573946457
318 86085181
128 150408396
739 21807203
654 20176531
11 65994424
675 1000000000
351 405031130
776 128571088
455 1000000000
517 8463495
331 57016646
257 252883085
594 203533945
742 371543728
38 140202845
794 895087274
333 32348052
262 205819916
624 60386366
530 253181948
662 12579269
422 1000000000
265 332262217
457 1000000000
271 185140137
709 26726811
594 170525585
352 212101584
568 198254961
515 49040370
522 159742790
565 216731913
655 362605748
768 476623636
465 6146544
170 98060109
470 7137187
29 75659078
135 299967248
319 230301852
588 264589649
536 1000000000
525 79714526
370 24319184
241 23416246
275 12326004
706 24048959
165 1000000000
518 268057183
718 8862683
742 168017835
119 49631241
489 212895801
423 471572424
505 20083575
584 1000000000
252 4894422
448 269225619
252 210266438
312 936764292
383 148707510
632 211508924
334 15599469
392 175815099
624 22010626
144 922962585
175 6753976
695 652703659
49 305812075
646 90434408
639 191794231
197 1000000000
417 243137602
412 96823992
319 1000000000
115 304829664
320 156288537
337 194615174
206 483478217
447 689485956
15 342050406
773 19791227
780 410160410
747 35980465
301 156616815
761 76699791
153 22124046
470 148531045
26 7565882
620 380508867
534 74821492
769 47383171
566 112961278
766 38557400
258 154081984
394 1000000000
97 6065497
367 35945747
509 74333867
19 164546568
476 65290400
160 1000000000
135 358602082
92 65237295
646 477481502
111 8138601
65 1000000000
35 39457336
383 121972328
350 168993025
202 47475194
170 4605743
552 615743995
269 27934627
34 224074239
688 246875631
448 19865095
506 1000000000
73 677613362
533 136969433
743 90709782
455 45586576
224 44571895
377 140738383
605 135170333
403 1000000000
646 904336636
157 277258088
450 653814277
575 325771
27 1000000000
736 358216998
215 480003331
137 16671210
415 309183788
98 127604296
411 1000000000
339 2151823
691 31667038
68 200841975
302 585447717
604 109671522
150 33431389
228 557627975
273 19306653
708 137294558
552 30239314
452 69159306
163 77337116
748 210726678
137 1000000000
99 1000000000
740 36760352
435 77802779
538 139076810
610 3707635
52 800500646
505 65387652
26 197086257
319 3045050
403 2387448
478 117155438
617 3514308
348 689440715
290 57270659
195 345640158
167 1964755
665 143500509
544 722349316
102 370511943
213 546275388
276 289468617
653 52053161
745 270736726
754 277501795
303 206424901
362 1000000000
748 137263528
62 911321395
329 65817864
278 173339345
173 524910210
473 21746234
2 1000000000
177 255848202
782 407518799
228 220013284
378 203103682
411 1000000000
14 11058249
574 18368233
594 334988149
84 56819168
110 71655883
359 481179074
713 155768514
93 34561341
524 79785658
479 31147537
223 1000000000
117 55440219
234 20757852
135 568207736
149 49602231
636 231751568
327 532543612
798 250822811
137 48297753
83 25391890
35 151377072
228 1000000000
253 331064827
217 1000000000
703 708327653
793 432204536
304 658678541
366 102446702
154 675375000
670 462753483
387 143640041
178 26928853
628 270924156
82 100610909
148 104710982
197 61443749
749 1000000000
661 1000000000
261 224730339
488 736965764
486 995184366
7 334830558
726 418097348
698 1000000000
221 187859665
73 74782484
709 72602132
635 1000000000
532 181178334
474 921936736
84 1000000000
236 406760935
363 155303129
282 281532641
34 1000000000
204 137950667
160 42860793
297 8375249
783 111481504
763 351849706
117 37520493
712 170855597
603 12600663
185 330508448
137 1000000000
502 103179519
327 204391785
742 1000000000
733 768536227
531 127876636
178 2740851
131 46307099
303 609265885
447 615069311
156 851867260
623 28922358
449 69900636
27 4014817
646 1741485
394 27972193
466 119791530
518 4867405
206 201526932
373 45580006
514 67982197
384 114115718
630 17496185
591 512599522
434 266213950
201 327334489
29 134429444
632 42552185
609 835336945
610 433916804
644 32647980
560 169146567
783 820432227
138 89998488
138 152092245
599 221384625
764 41763130
481 66290597
206 280385462
526 29009156
393 140293507
103 57796718
179 360683945
404 1000000000
340 173231004
93 53176166
246 656974301
9 89000394
192 253535622
130 73077124
377 149723650
142 94292815
458 34727502
310 123416442
603 9646383
66 1000000000
115 586590597
313 34732831
444 476864470
581 149996902
60 34924874
12 161009669
732 133851496
727 62659199
196 162304654
366 170608146
92 54646736
312 75238812
140 256376801
159 763999650
219 166409268
361 19374854
754 43002498
383 25501078
377 126927795
425 355390360
280 2500215
335 35908739
663 47734055
280 191325724
797 22671531
78 1000000000
371 298817334
535 551550275
673 4025363
60 1000000000
271 238391721
581 1630818
517 16058764
569 1000000000
170 557095337
546 727752372
360 200941868
614 5825188
709 116475103
558 326121435
42 1000000000
514 5958455
287 1000000000
233 30528408
107 208392491
589 312304137
375 580605500
788 1000000000
172 937991207
423 345715251
560 105660458
686 138576034
267 74373009
497 1000000000
519 28000442
535 26335227
75 93069676
234 119804521
254 105804262
80 268229373
9 167389276
274 128099115
180 51348622
696 113282329
134 103899020
73 4673193
329 98306735
687 490711441
67 63473585
240 6412771
733 50543655
565 117953844
95 14624330
518 261952618
369 83334966
458 164858288
251 0
395 9540610
708 110502669
143 335650605
661 36656420
319 152182275
694 1000000000
483 120517422
719 261393531
483 848842542
8 105571316
422 692894536
200 39659328
790 103678433
472 328568047
185 267776219
192 173182629
472 290380951
168 18760794
571 69765701
632 55704326
681 285204937
791 489124216
492 105322584
623 114001153
714 71224030
166 117205925
204 241184143
357 286301596
698 181799105
628 175854247
603 285188197
666 140400313
601 297085345
256 191625618
730 191614965
751 130668548
423 274656087
77 354442616
616 848791752
258 20131244
37 1000000000
120 48851610
645 380891285
630 236878611
434 37293860
323 242752169
466 943946
136 248610936
494 955672154
45 33980784
750 11047687
217 321772760
633 128804316
662 36597933
729 93944670
138 1000000000
308 256871851
382 490681743
659 656733260
378 459628803
62 92794792
422 40188051
348 367965727
362 690335687
343 683763286
333 197573283
437 513231913
728 114428596
479 278668126
595 46369828
221 598746348
70 34286810
503 107295661
441 269562008
148 961661324
339 34054761
798 492117492
253 146345511
763 58636397
255 757748893
628 355148193
385 151209351
241 40579003
11 600505570
441 671089326
100 138137907
310 173362473
22 911960757
366 117517300
583 376475
426 627213029
800 7364089
786 228494472
137 1000000000
461 28058363
41 41362595
357 528976154
137 704060690
96 31142605
18 3859902
167 222121500
458 279912477
738 184033954
185 95704540
729 210926
649 132570036
115 502500785
417 102382876
442 1000000000
616 1000000000
116 141307398
423 274431563
298 159382727
486 1000000000
548 63363519
652 284076401
649 295973359
707 49244546
515 980559539
593 1000000000
184 31792835
287 14242382
625 217225517
437 1000000000
150 1000000000
699 50538909
398 1000000000
57 339307338
579 59703956
118 50539254
667 17450459
571 124366957
479 1000000000
208 366662625
119 562633145
253 573287519
459 259225994
618 62755780
66 76525047
158 386430648
38 15149189
738 7461180
477 27034247
350 11545594
16 24277589
570 202456705
359 5463639
254 241225133
169 631179726
785 8861402
576 93210129
221 16647281
466 12748154
584 170879911
744 440531923
59 108131388
42 37439978
126 81568220
447 2653662
120 33931755
369 960794983
499 89813660
518 476785629
277 2589686
679 196109880
551 2882256
60 117074830
657 1000000000
237 652267232
794 957397381
577 71596315
492 4395118
34 332045077
557 1000000000
54 2402365
454 110831605
294 1000000000
63 79799333
602 47092468
671 188299893
729 44161
784 46838704
621 308316619
312 225552101
316 9995171
256 104714034
527 146803461
656 17391042
750 105776711
784 46599964
768 422673633
40 11548196
271 120073611
63 41922061
705 2259891
766 36454554
575 23409249
45 100246055
81 191777048
532 342338905
703 38553790
699 37556695
48 1000000000
361 691060578
302 29226396
39 73644363
639 246780622
413 24140344
492 129860037
51 218624526
509 97712837
721 51364039
729 436271638
30 558008626
330 10780928
228 1000000000
534 33037413
201 491154364
358 73390940
566 265178770
514 3210954
179 141382960
721 70194141
391 34145331
189 315001964
348 146906088
524 236377951
760 283518883
359 526947258
260 137792075
342 3025365
456 178357338
545 116831666
11 24319825
143 68711566
631 1000000000
138 45705300
274 48190240
248 397912913
453 207786068
162 406219985
88 1000000000
624 105474472
50 57940575
713 22307910
477 326069942
119 327929337
127 268482900
384 469101021
769 412567052
557 132248228
331 1000000000
518 438579793
549 83096405
242 1000000000
663 340863335
667 14274349
232 163966897
199 1000000000
129 28982449
511 33835363
298 1000000000
331 25263177
683 50262203
371 3211024
588 58826912
574 243360311
84 1000000000
630 6867098
588 570094022
97 246027998
412 114691022
40 306134248
236 240455731
691 485134540
612 1000000000
105 304268271
459 359922226
52 850502899
555 104907467
154 941591273
522 391709599
4 724479047
401 5141062
218 375897171
104 113799361
259 229210293
214 299326541
649 720887893
197 756464813
114 1000000000
219 191399451
487 2174443
449 607923226
560 57936867
255 287058828
501 295781208
220 1000000000
637 30150971
578 101674893
498 363016605
759 1000000000
218 1000000000
484 212666805
798 433814293
305 94004990
742 405931661
677 236275965
409 597704553
746 133277088
449 1000000000
6 20215121
36 1000000000
578 425085143
619 327014446
582 539430560
798 288767060
442 35384466
196 295497015
326 30451115
7 787149518
337 998163647
685 492373537
68 272282400
63 469854974
359 218051016
709 55492997
546 35022287
423 168639245
189 36384317
140 586691410
159 668842667
94 281075969
209 52606174
323 342731379
347 1000000000
356 579960243
389 46549832
649 260601308
375 79559538
697 309581393
312 183853032
702 945932
594 95507800
670 211488886
619 78325319
546 158951581
748 91097305
498 37789145
253 1000000000
405 1000000000
5 502989418
597 375600636
718 112080349
344 482447312
62 21390104
263 18739115
62 139817951
74 991018206
726 84727315
585 39502446
493 850596301
395 49077323
141 371285631
538 87069547
412 105943503
508 352202506
131 1000000000
762 15168654
618 151356139
28 323697334
792 21079636
41 193899091
535 216968875
299 178501284
237 367711294
104 58211917
611 490006885
457 23970534
417 73378953
438 119210731
303 1000000000
246 110717886
693 1000000000
531 488687989
794 6322819
275 170319944
455 24748571
511 63846830
708 12382226
223 660540237
697 1969287
667 97078702
686 146138115
346 71824220
394 62469004
70 224148750
470 1000000000
229 340321565
186 84915469
128 19243631
734 233588799
799 53132432
458 4513411
713 78827178
517 36770213
232 48773896
601 27180265
162 462990803
12 175611763
32 359162816
711 175221025
650 341590915
50 875827987
743 489322833
244 25391625
673 76086070
695 65041241
670 40256053
737 265500595
295 27763443
315 8774812
228 132924327
141 163940737
285 874047375
350 175653717
121 1000000000
760 1000000000
194 121086708
417 700771040
638 50819728
34 82607136
566 148466800
707 259948242
338 1000000000
748 331128886
313 82462709
324 120758545
149 1000000000
596 4909241
140 15409640
164 50695388
615 50001701
252 103638244
78 109844518
164 1000000000
72 717997175
388 344214594
127 956530326
483 97273022
473 515260389
490 276625641
799 396108344
545 1000000000
249 179364348
752 88257270
111 32082390
383 202775887
456 162901193
405 39343786
430 162716638
731 4476622
135 1000000000
505 74253714
508 124053612
215 1000000000
245 37617306
509 1000000000
633 308155417
659 39105947
178 683938207
416 284258504
262 1000000000
429 31008316
798 180481988
322 1000000000
578 117793629
647 26820534
185 31153373
611 445084202
653 1000000000
448 112808539
292 1000000000
292 26479569
7 130963993
216 1000000000
30 60874018
356 3336805
465 1000000000
527 248649476
391 24570959
643 84078085
106 37496836
646 888056129
96 972343649
545 659531044
370 67644744
412 54678621
520 69522422
127 252221112
169 137674222
177 21575690
159 2290888
219 1000000000
656 89200740
485 78506267
229 81583769
791 179338301
6 49150250
537 104871962
698 29224650
371 190402442
171 178862128
652 1000000000
159 344832953
333 537517122
511 100767995
414 37173468
403 262383500
359 177737886
99 644211661
48 37019889
374 192573682
640 75248730
22 27853557
672 2389495
137 185430085
376 958400454
600 125592962
336 1000000000
203 120002144
464 147672305
713 110903901
32 177618338
732 190510320
391 6090546
650 12092004
686 240649097
508 15868429
573 258973820
538 59646005
220 144449844
107 42336699
50 106294483
569 489963026
649 21262538
650 73761877
295 31210338
295 21335367
213 396090852
24 209429549
59 70799113
485 1000000000
736 1967189
213 6045703
206 499716292
626 22568617
11 45261275
66 931971566
192 363410829
782 342636279
501 166268366
702 699585241
178 551159505
697 17932634
286 757098571
489 2158041
226 166223400
692 126708163
230 886051932
99 79220335
626 91491612
766 192591337
46 1000000000
556 120250186
34 82654434
471 699333727
85 57424780
613 613179544
240 394564406
319 19025512
251 67248743
493 314222980
446 93835197
343 43099987
609 175874972
708 10544208
363 95517526
382 39864529
5 784472097
523 1000000000
151 20597293
276 131331300
745 294011508
609 1000000000
643 398442488
153 328810460
45 168090872
102 173713342
142 99015194
46 5041112
399 286839812
122 131876598
664 381738263
82 68239851
177 456821741
157 18807498
577 13688163
677 47760358
82 292673648
560 13183738
490 288280120
327 204257226
242 499943576
466 301342217
690 241488585
57 326885623
657 18142915
67 533998445
185 79730329
602 366528649
528 15309053
68 21950200
575 263579627
106 234345003
750 24769774
180 349049960
453 168370823
521 123594039
715 156811367
115 111863866
521 26379821
632 33054009
679 117572495
385 138915159
13 57207722
790 13709385
99 220146365
158 177229024
209 110704232
227 399174967
670 226491814
107 114410160
211 309338918
31 231441831
408 1000000000
199 81685685
53 45159033
491 73424358
402 189579330
178 243948568
502 270125778
358 646383806
42 46405243
621 284138329
374 249259647
560 117915994
194 3646784
279 1000000000
214 342371619
361 183476109
410 154193853
496 926697
501 194426244
50 56076070
368 1000000000
120 102891484
435 603219386
234 104493520
390 355804183
751 20932563
432 57016483
465 27766854
411 1000000000
726 64128179
365 126771257
423 45535506
15 72557737
12 237876712
169 33753155
333 7068645
130 479618984
465 1000000000
356 7162510
674 473326747
277 278721813
742 3991826
94 50257488
70 260749892
455 768481439
490 1000000000
24 164155259
153 393932843
88 11970184
701 189854611
688 132780350
60 50796129
745 17133230
767 56284719
648 101958928
270 199116641
792 3252315
369 158619245
544 5341536
527 4286735
743 7774068
753 200854947
406 120306568
479 44664301
693 248681137
385 62922779
396 1000000000
255 121161394
35 131181834
225 60814503
225 42437958
430 224737673
79 363195347
719 14564581
726 180470266
588 822399565
251 772485075
621 1000000000
457 652071676
793 317646127
775 149486442
634 481247453
124 148414066
566 55363258
497 12150425
758 1000000000
206 293231308
322 125440771
347 264170080
162 7720955
703 28206484
285 302116240
68 1000000000
732 23567659
528 44808692
39 8749811
524 127156438
710 42071170
224 180351780
257 349774463
499 84666101
512 488233284
207 130248149
458 303710159
282 85204750
520 316827592
509 79619889
674 1000000000
576 21802933
672 13764467
363 92773949
41 296627705
741 101591836
679 28270101
503 222151310
608 823867346
426 108961784
349 936189203
3 545439684
390 321127262
109 323880861
67 299749951
335 130342106
731 186302076
432 176578391
599 109078099
441 446618443
383 82963475
722 643499122
731 1000000000
99 136665474
307 362679584
20 185119431
79 148755635
12 707805781
214 1000000000
436 160460134
689 665101793
213 73082891
40 222061738
116 520879429
611 371565326
796 81185581
489 17081610
788 117681216
452 129058716
611 587292085
570 140235196
370 318323514
500 422526013
457 105640127
442 43280153
48 407868898
788 900116500
686 23896624
297 94252526
269 1968201
450 219396518
115 1000000000
583 605000
265 73957269
192 1000000000
119 28721115
437 20646470
324 112561772
686 101963407
410 22411250
242 192840134
95 2727316
106 41719571
636 1000000000
734 39276461
665 243896032
278 121689355
382 434592721
217 1000000000
658 144237141
369 26658566
414 10360207
644 102795150
363 254556325
411 61384694
94 3215509
318 92222847
674 186518052
85 30128818
414 1000000000
423 174347731
793 1000000000
317 36197445
668 81491549
543 55799312
591 219374928
181 316981690
474 1000000000
711 19633649
485 1000000000
349 39442934
343 59169478
350 907751627
89 363041527
243 221493226
404 70361825
484 74757836
141 286809387
377 684239068
463 102372393
217 708854907
705 9854191
558 75781997
362 461000194
734 529904076
563 3406321
626 353924898
260 256998386
626 91391282
581 13998209
486 6272491
573 271898223
181 208407
566 90134082
8 34779303
182 1000000000
199 12686944
646 182566588
250 9349200
14 69672339
617 307083804
53 58590870
700 3365221
773 72253385
410 199638209
260 103521301
748 284628944
699 641781445
26 343708222
338 640740
108 404785575
241 214335762
201 563194966
799 26410999
187 208401609
421 135037496
776 307483659
428 146669657
249 1000000000
281 462272183
598 72002203
183 125840470
647 99847206
525 24800730
115 628525551
34 1000000000
3 49538203
319 103763633
351 264022395
492 776399835
655 1000000000
17 16379422
251 127121093
86 177513365
523 227314699
258 33903039
774 751805202
478 385456592
245 65313667
307 539601499
160 165006152
294 10918747
79 184127746
66 240688383
457 313280408
14 521724292
568 87182255
369 94921990
98 45707619
564 9298960
592 227067985
447 3563988
458 202712873
730 95093550
440 219661634
492 1000000000
513 72872992
287 142581774
14 250444159
473 21901789
359 450163852
707 1000000000
628 34937176
5 18615952
669 152769259
742 91134016
490 160716395
112 242757537
642 351412026
585 103224960
14 1000000000
154 73729114
406 1000000000
427 57251878
354 74466270
228 4198100
569 1000000000
12 1000000000
37 108188539
204 114253881
652 20430159
269 1000000000
535 39174899
725 134402774
46 197873522
620 531715570
121 10349026
92 30164055
319 24726792
715 272544529
9 33969340
386 23755534
575 148139218
425 309521
553 46172190
104 87116209
207 17683841
39 224117283
217 92494551
621 40901111
46 359398735
516 192646181
759 278566673
530 342695142
412 205612078
95 113295874
357 828156327
725 65891649
281 215411221
123 108623339
66 240652643
600 450426520
582 237636409
405 95345476
718 914643295
154 177473740
738 68107287
495 330576532
106 415584795
379 727079155
301 110693349
456 170581031
660 219717224
572 1000000000
167 392811914
768 1000000000
526 91695982
572 1000000000
625 43615609
727 63586780
568 61843552
603 403108232
714 255626678
782 142609233
144 225342556
729 197517017
274 539332385
580 71860014
760 182035970
535 224495801
73 104753086
153 52177271
303 266972
723 80644679
560 65971106
622 107744103
53 10944833
688 1000000000
358 219611167
257 36858458
427 395500621
779 1000000000
715 262456437
212 1000000000
719 55601298
37 348699716
95 142056173
646 433295409
739 628615722
223 348755905
515 368858521
504 15817696
743 100777776
152 153542262
694 9296735
9 838316634
313 755247083
465 126348557
56 84963684
792 169455374
187 282222581
232 377207315
41 196825508
264 84078093
172 3842000
95 46289838
746 3358017
566 52873215
684 35788284
213 142859812
602 6715313
612 176109491
92 100929093
746 1000000000
345 1000000000
273 5736996
506 600982711
543 1000000000
743 178275262
61 1000000000
200 389660799
83 140753837
101 322427243
360 254326055
710 109080675
518 1000000000
402 43412277
755 73911885
690 244658296
24 1000000000
494 127557704
541 130870161
718 281514084
554 1000000000
441 32708437
710 186300658
505 72832484
570 226886373
500 310607907
175 265520555
691 1000000000
619 286261338
94 22807733
758 137459214
93 234553702
474 29980358
183 383636838
317 1000000000
533 120185052
168 160101002
447 231087130
163 82293163
189 19863411
310 30417933
663 1000000000
169 835504751
501 231801793
355 135222332
510 1000000000
110 729657694
123 24891733
176 23753199
436 1000000000
113 173815503
17 249634179
379 134383400
633 235581084
85 1000000000
310 90512629
6 1000000000
110 225353827
695 31953640
778 340944774
528 143998852
594 23835202
665 327648811
654 32068643
505 49376618
357 1000000000
410 4386055
576 89519043
354 210280744
647 54115302
314 231379803
610 255731631
714 255087182
441 269231279
409 87720917
564 133743648
465 439469769
186 330244993
504 227733657
372 146964210
23 515469142
458 737404082
566 526710852
516 35722240
61 414162250
361 167202581
211 94455546
739 12118298
193 1000000000
152 1000000000
48 153493738
433 858550
422 383727798
86 987300743
683 1000000000
15 167979449
329 50407349
291 30945759
70 134106205
571 163339036
235 126640592
159 671211929
480 149707252
119 321415082
333 41277850
523 42800628
186 108189927
35 6358985
14 153968047
6 1000000000
371 494071315
125 121801031
175 371415297
592 176638822
74 285720603
231 183693379
558 16144732
777 110517484
770 787271988
480 182623154
13 4257702
722 23025131
600 173195719
264 5700582
395 351327111
330 223467177
174 865780898
800 129585115
360 258488852
145 51346184
547 47915576
550 50952714
453 381493380
487 445983712
791 593047663
636 127866240
321 184345005
653 143761001
330 44047178
770 922862062
444 1000000000
482 285458712
541 94998323
86 18362222
566 96978460
422 924578250
623 235425982
154 156982678
528 1000000000
121 1289587
384 15039027
749 72673520
329 42015748
700 47168583
433 31779147
175 1000000000
481 25323536
526 470663437
640 10053664
193 1000000000
632 175143493
463 1000000000
431 101801847
417 165216222
238 147723329
31 1000000000
29 1000000000
369 488562964
356 259767632
735 149363889
587 630198368
689 121927093
665 191387062
430 106233738
152 78274784
223 949983882
142 209862993
172 36416489
292 165959196
157 127738134
33 199322118
217 693708614
655 1100144
170 146693124
52 231189887
790 1000000000
57 235453841
70 245019
582 211102488
642 169620905
131 204379024
370 105009695
663 103531936
125 211570811
524 29209988
588 168554615
712 346837475
743 501447897
660 281530770
214 21325448
440 96843906
1 23174376
59 349048554
240 99992244
647 77235596
714 167933369
706 56661187
184 266608407
245 157490456
450 88306718
424 22748295
112 8372129
547 4344895
585 324797057
461 94715152
151 23125700
48 338822821
64 14739895
626 37750792
525 70011145
124 424190
742 1000000000
53 106846989
243 53409507
231 809426623
27 16818197
376 295014484
391 86903820
625 893685029
447 124652556
58 5473105
395 1000000000
219 348080606
51 173934137
252 132946775
575 199864725
68 120493378
278 373870964
125 106134659
417 42852865
781 1000000000
200 1000000000
125 4276580
115 307724288
660 92007084
169 325263122
668 164524089
180 337557851
507 58630029
538 15331948
730 54505148
516 34271182
449 271225207
58 1000000000
792 106064935
708 728158084
134 104250104
105 109033940
725 147882977
594 1000000000
683 226836172
103 126998354
401 330159789
784 463554403
47 126538983
277 1000000000
44 76740868
318 31167971
114 1000000000
498 71533065
199 6546872
538 211871378
20 1000000000
286 12114391
769 1000000000
774 1468417
342 111798380
793 283445543
346 109220396
65 480145835
215 31300803
324 1389558
467 16581193
491 203270907
727 1000000000
94 969506798
298 34060483
677 407794338
502 98360244
583 143770370
321 114952440
653 619272491
84 141845869
160 4859545
791 1000000000
37 1512661
690 601829811
519 1001125
205 324470783
269 152268406
111 68163480
254 14243300
770 175412053
163 141881815
236 569829693
292 161599001
150 292434461
105 15993023
7 157795262
250 151230768
233 252914685
670 587992174
354 37009985
254 26251650
603 209798422
770 64178482
444 313678576
242 218388842
493 247571425
438 40313047
309 298027039
597 183255803
798 401454695
728 12321474
302 163502938
424 1000000000
462 475372289
202 7758344
294 1000000000
265 211527865
61 1000000000
684 1000000000
157 585414750
250 70640603
12 1000000000
732 1000000000
627 13173757
154 693990314
730 12943145
380 30825760
73 134388977
74 159719660
679 895508527
459 727407584
222 578705030
744 577267813
788 87913265
585 110987771
242 810358167
278 113322402
63 24740833
55 120875639
549 133365822
755 2252820
650 89113438
19 121418793
151 532009627
736 107951935
660 360725995
671 199422705
457 319379904
571 73246970
158 2730321
155 140896751
634 317389351
6 423930035
71 5760027
645 317442616
619 17658144
448 7959285
271 11270798
703 563148908
698 1000000000
362 879231999
726 48770873
104 1000000000
329 257304923
322 943580601
124 193982060
32 294828618
87 120397044
234 276404066
34 237934528
584 366514717
676 84497902
545 17231806
743 560434068
798 336994342
753 64797270
200 382543167
43 206276175
740 339413618
509 44559357
509 199405235
622 291640473
282 205327944
552 221325472
738 609159780
209 287414344
606 829535897
50 32256571
86 333833188
499 106224923
402 306747
412 661326326
122 30198921
468 401678685
469 360643421
517 50138611
12 4012979
245 21834094
263 14203777
781 91796092
782 52039370
500 240931791
329 187711032
84 87710963
319 43062161
83 1000000000
153 32646490
539 12303959
768 285273865
210 239304139
601 242628629
224 393130339
47 52234763
175 164775376
169 100910970
517 47674560
238 375530
140 201939035
743 49384483
426 99125154
60 34166417
232 260147051
597 208249297
781 1000000000
794 1000000000
227 340529483
498 11293725
784 112549437
166 1000000000
61 99522284
382 410862968
50 295098903
482 72033623
407 901063673
570 18180117
691 718765566
461 704637031
464 164773271
740 138356315
116 77906079
616 249512956
296 178369439
478 57041992
372 237913585
593 1000000000
159 46281376
520 116561020
371 138387580
138 546853460
342 134344713
96 874294628
401 247056544
50 821224226
44 36996071
552 1000000000
367 142027468
778 1000000000
321 6168043
703 12200879
652 2081692
48 122891785
182 49239013
133 505788192
72 363543011
262 19677520
457 1000000000
539 4128211
259 76427266
683 1000000000
764 326336625
159 393434719
574 137621555
640 1000000000
783 168287380
691 326704615
23 113885085
451 110912206
256 396790308
471 1000000000
656 1000000000
534 319216407
529 437869240
73 116549155
425 685613233
600 1000000000
65 159155264
747 388439877
256 597061549
106 314579688
80 24637191
764 165556511
183 582100797
394 263736502
702 162844597
796 91469445
493 127054244
122 37957150
76 9443248
204 77103261
2 120718342
633 47534518
281 1000000000
394 82700862
23 171534560
648 30275013
5 747443655
344 5701
491 519146822
485 35063299
560 19023110
630 303714441
446 569063997
274 206999640
347 29823609
610 39821314
752 19222662
302 49747448
773 271002002
670 178360371
578 202459279
282 229246360
686 103650067
201 283966926
659 147700067
596 1000000000
471 1000000000
163 398963402
611 65298982
574 44921096
638 524628144
333 268060959
210 1000000000
87 113967564
293 140586667
613 103006089
769 504523600
768 679019132
364 309371895
109 172795069
270 20319390
279 198806874
49 1000000000
581 220633944
123 56404968
574 252122025
310 383566399
235 189894291
648 14960250
52 1518537
378 1000000000
577 154566166
339 240951410
794 6916298
125 132425114
102 217709711
702 342897834
174 72114728
191 16932922
410 365990885
72 128424129
466 1000000000
321 554656860
286 4717716
721 204254080
325 28784353
290 725586512
688 4581466
26 3198148
232 349715206
610 191857737
722 159610715
354 1000000000
569 214103948
225 199224683
356 352053694
361 3824029
410 912364480
384 56191103
68 54593002
623 175329885
234 54742572
606 2102504
468 257410174
149 788355671
10 1000000000
795 255624970
499 987608465
442 1735
600 261146549
696 1000000000
769 23827123
670 27434764
758 77812250
243 1000000000
255 254029463
225 739856086
227 136083233
238 147831970
139 328438515
676 212286022
352 5131183
297 367706034
391 259916438
581 270111789
459 1000000000
354 114541781
723 20739107
70 50879606
390 755310997
219 270423637
77 0
167 1000000000
400 34948231
243 100053976
599 82192609
710 8875941
746 10514209
714 629002026
304 59242069
325 570502047
210 77151285
352 297460782
56 47937649
259 113944215
522 109760050
438 71779118
400 260878637
641 402698228
433 216945956
683 132329614
214 168079237
221 188479710
200 43039693
607 52615510
620 1000000000
249 775266686
781 102779663
499 560774108
50 380979233
340 69225592
770 904624
709 81246995
38 513763959
750 117484393
262 64905905
87 83036359
554 98881158
296 1000000000
730 90174023
200 23188253
637 255599236
385 223429364
412 856272003
89 135595107
63 171951685
217 877975532
558 130663664
168 6733994
369 17821553
784 405682352
719 687033893
791 176878167
114 15629597
71 131301561
576 262901874
454 103982009
482 945248221
92 326149713
671 1000000000
371 1000000000
1 852689939
209 843300829
110 330222497
800 15498136
335 102732439
166 130733440
716 358731754
236 88933572
77 13200362
281 183283983
410 187205783
407 366390257
90 101279060
268 22994790
374 75697173
673 66030423
566 19151860
158 273844815
162 190891148
331 109678444
578 242144145
496 77636730
509 145824157
436 10463556
221 1000000000
320 1000000000
680 594143092
444 6113285
551 281623618
784 49055606
225 190117237
196 68915559
288 109554748
543 226590276
426 124199191
426 401404240
232 799383653
237 596988511
386 68877102
752 44827749
800 1000000000
667 1000000000
42 198733321
373 45200393
487 38939752
328 30975977
640 209725678
602 20379946
285 1000000000
116 161616047
550 372946466
61 105711908
611 532085048
735 244434575
699 458941
480 3929536
440 1000000000
266 41531302
640 17916473
643 1000000000
28 335016853
115 871867488
723 20282228
260 322579506
783 171909781
156 657397488
438 1000000000
101 194809953
625 18617854
773 255265995
744 875572544
645 60998064
131 59216664
428 137110380
458 79000582
772 16798347
580 50484151
531 12506000
122 207955805
450 475556438
244 1000000000
729 52695151
666 25334668
352 10528438
244 231491562
383 37628000
169 222225285
445 327333330
643 1000000000
515 131419838
712 217584531
761 254861688
225 152553902
711 199392663
181 169107070
789 229059325
142 114291257
586 453678489
722 27210564
239 55728675
394 368333946
204 114573443
30 147160944
553 14248907
118 98429427
558 41707867
474 274270170
66 1000000000
625 183363073
687 34893000
548 58576565
443 8037272
507 263232729
271 125013971
286 15213421
658 139200908
501 1000000000
334 13439224
39 271343930
521 178191734
254 82364947
333 179923598
32 80492408
544 297563651
438 1000000000
362 349843749
711 259529711
309 287354149
157 124670314
71 282124938
734 401859513
426 5556711
179 67792245
68 1661975
196 1000000000
734 412631451
153 1000000000
319 13170085
762 17224424
305 217287188
686 657725749
666 267956485
62 9868208
451 707326451
626 18521680
404 515028816
274 156422325
661 200759598
166 1000000000
302 153607686
213 2230955
70 326405795
521 67681504
198 21095556
40 29543380
406 830914439
27 391194292
126 98638911
521 338493589
230 236342492
732 407950553
117 297479821
26 580045316
20 604992295
12 73387036
107 70732290
122 6068913
130 13650308
236 1000000000
193 123765111
234 23030148
783 410146427
571 202102509
374 26561626
712 15825737
412 1000000000
473 33146786
778 136605329
246 1000000000
423 607368855
711 160919225
157 122839685
371 87329130
338 132215099
324 195630
48 345153915
416 562332548
221 681203405
80 18164631
513 32069520
187 118833493
614 178660780
491 1000000000
690 250790602
486 97247725
175 52585358
21 633189857
195 504177468
448 308579556
407 390978292
559 127407588
50 77793673
586 21391031
350 1000000000
760 1000000000
481 150039702
34 672294378
100 316074826
368 295462973
495 81721322
362 55087359
362 59400047
120 284690962
669 299106545
97 233453894
719 52425787
783 130179169
265 14278575
40 132417569
787 16559356
341 96526991
725 286880817
541 3529030
279 111501020
682 206331801
576 538556444
706 49828484
281 137669172
46 1000000000
618 1000000000
150 155059134
219 139493182
514 5717010
660 79860342
602 1000000000
732 188412500
709 258326015
61 10121738
716 55840750
93 9339604
759 19541779
101 583134311
398 272726427
637 116441550
57 88344438
76 2643016
31 139996906
123 163495282
106 75781736
435 555927631
800 510013001
314 454158383
202 20573216
248 10596063
591 597174692
439 68175861
185 34371475
542 646621730
334 142025469
468 380815829
759 300033672
674 616200050
316 481605892
688 63807588
197 206721691
517 1000000000
346 33961044
427 273330812
162 37016906
680 312069121
294 6384781
485 227616622
270 33237395
490 210281485
418 320039911
31 921619090
266 12947883
140 498588374
461 134296831
664 6689379
405 334797591
780 22627083
264 277486491
624 91030977
239 551900058
268 101226153
433 68753075
552 191651545
120 34968623
747 214117653
554 833871590
510 228065446
496 149430089
521 53330503
690 1000000000
532 1000000000
568 85127104
551 368806628
458 699750646
713 31299126
719 374805660
420 73973247
400 101013810
286 300561896
149 14810867
576 1000000000
358 125050885
146 81292992
491 9378294
187 143360154
203 415939344
772 1000000000
688 181069872
790 1000000000
768 436046265
663 275228662
324 74924735
239 369976397
483 104623832
72 318499990
615 472144627
777 1000000000
182 246725598
313 5190808
89 313942382
353 171702306
536 38549970
745 63714037
123 125780363
600 59770562
746 103646493
408 85777577
12 46337877
559 93359291
266 234297706
486 11167403
204 125723573
453 570628133
282 309092764
52 69272517
60 390617346
603 64107246
313 165012174
289 102853005
91 386224325
111 290355250
712 37765712
557 342168317
361 192217368
739 667681527
677 135024879
89 1000000000
166 29014674
566 397388460
274 153347103
483 424910789
626 214437454
168 884887578
526 41011871
269 23693626
238 320792961
346 12762676
378 1000000000
182 392761968
249 287507878
363 686786139
500 763716439
191 703821142
179 387547901
539 89712449
126 45097737
679 1000000000
285 113587575
426 86399655
631 69259092
653 274652171
374 311100490
665 525853925
704 110004118
724 118934045
446 157783690
230 43812603
23 116203773
729 445151082
149 148281447
564 181105915
382 486909673
446 150875558
603 137593018
224 95495121
148 3980118
386 1000000000
657 17931835
779 754149023
250 63145499
453 1000000000
54 46142105
438 143173441
270 367973519
263 66846654
618 188955351
544 79028722
722 131956533
777 324721588
302 97765200
714 1000000000
421 216977157
650 375274626
353 148051702
82 11935554
328 657389178
650 913441336
227 319041430
666 126134279
25 136397484
42 109275432
116 243540582
673 19787761
186 167365022
136 49761905
436 25201003
647 24968547
362 9900645
454 1000000000
612 76539814
557 4583288
298 42290706
419 190891264
131 98246851
786 430848041
408 10649034
768 55044731
593 470766896
790 454613431
374 615224059
28 106483801
687 105479746
89 49935305
67 85627796
406 184358405
796 115960197
796 61253754
448 110226185
337 52142372
280 318002380
797 240366212
331 185069771
554 358895282
387 23634603
799 208033244
486 341031225
355 361588515
349 43078906
351 136855763
560 68973616
731 130622233
199 144235787
446 92538895
426 175411461
274 102290089
640 1000000000
125 732257685
402 354527621
776 405720255
648 10369241
251 894963819
330 77987604
318 264064791
416 5619064
345 613496
465 88179622
307 40094990
263 163000344
85 1000000000
328 169686473
199 472231344
701 11662870
81 254782277
493 388528378
251 1000000000
642 49448558
780 123180382
354 24981773
205 269315208
566 54454152
326 229802315
678 288233781
703 20811935
250 331282211
32 6737597
666 61961666
720 25205210
461 864925421
281 209425741
220 412089972
129 104269340
143 322882788
625 293165194
782 21857936
81 578038582
225 342684896
40 423309707
207 179017948
608 484534628
546 402330477
95 32310647
640 1000000000
526 159651644
114 378540489
277 46616772
31 57786297
187 33849987
17 292570909
682 273723276
654 169631344
712 186573050
31 285582971
94 196382737
684 849890407
52 123448349
349 1000000000
625 300334026
186 14815013
767 1000000000
74 177342178
740 69724026
246 1000000000
105 281299588
614 133311257
118 117143511
546 676174175
403 167321324
626 322625853
552 35127926
221 2053668
668 172223321
45 151274977
536 28401882
104 250673133
644 62601756
375 388162951
360 30282322
545 364104011
716 60672768
528 167802354
631 198616824
394 86615874
18 67784390
376 1000000000
581 479273387
514 6663086
376 1000000000
496 414061607
531 688876513
586 371401557
669 897748734
663 191146882
96 630576595
96 1000000000
2 242587117
365 102913964
76 32970568
38 32374441
38 4497816
595 325777138
343 47219998
571 90752597
297 419412335
552 3138569
290 203542396
96 156025001
203 48386259
44 174883616
204 53085643
307 7064856
140 404855907
287 17347215
533 63084031
566 19910355
397 177499379
129 600838385
509 36524549
296 542160563
461 31013302
83 13606640
324 86341190
42 19781679
428 25825551
148 93760852
395 5841876
154 332320918
714 12018638
484 95940866
497 1000000000
506 52622634
744 530752
388 273021648
663 20947278
233 136948130
101 80167508
51 109090535
27 1000000000
744 695195852
193 317096895
753 85132837
159 8599042
53 22681910
541 909978415
638 291281264
226 13873366
754 262099233
183 546321748
58 396709717
100 470769449
574 269054367
529 833014659
70 3531532
70 1000000000
218 84551092
746 129101819
97 1000000000
263 265201114
132 229424929
547 109146479
779 207294265
519 119441453
510 481337897
731 84430463
5 675113116
358 704759350
711 47096383
626 31193136
46 52860315
709 125572194
192 457440697
8 721505356
230 166257664
675 4594891
359 211274912
29 73770593
13 15554196
128 155299542
30 313379660
18 226630199
707 365288470
796 1000000000
484 1000000000
70 283868422
617 97864629
183 17080908
378 84156687
633 73328693
350 55230676
626 75073955
190 10625295
107 327990950
418 123946357
524 1000000000
18 246059969
573 60989512
214 1000000000
550 29001933
53 626165468
526 115592507
473 64612620
190 1000000000
296 396187550
30 21184537
11 155308482
310 329956496
361 663188677
110 1000000000
492 310051163
653 1000000000
506 266740763
252 1000000000
572 234854243
483 249314796
570 617453439
458 34406822
636 8735956
729 767848812
10 214262320
439 290558896
395 36895249
302 276713743
200 160334203
36 2099346
585 785724138
514 396367428
406 283291299
144 425557208
695 40513063
405 46961295
691 106673136
155 59851810
116 99364720
328 84551578
32 59449294
613 8720559
256 338148928
698 75220533
315 138169933
366 333901090
443 79628524
171 39067638
390 51053731
759 94625666
645 96442960
59 1000000000
544 379005124
223 512211516
447 333921031
522 402763580
490 1000000000
38 97086146
296 122183206
185 51422378
610 455727580
140 245692174
640 209580355
711 1000000000
586 312472991
402 698196894
200 6615187
501 209022473
705 578117652
183 156051619
543 219377768
609 465026733
392 57467333
731 67305531
293 110451210
333 175594915
189 65611853
351 11860463
666 241600903
792 237651794
770 68654055
737 4859338
62 50521523
546 113466861
278 233348442
643 154619462
114 49452768
716 258023370
474 1000000000
133 247797386
181 298246262
629 339500766
684 438950715
613 112050413
295 132063927
285 286382451
174 340349729
709 189702270
393 128793
260 257610461
31 151100560
516 255691426
218 688845782
491 268336241
512 258458459
482 22519465
282 132496065
273 1000000000
271 270926644
287 620135802
233 842173513
342 223635424
558 421243401
764 59551151
487 172800013
218 123772116
28 184283681
184 1000000000
661 405905403
510 32881156
666 198973836
51 75655725
626 301135192
448 273184273
646 970235277
685 83240485
510 63475678
482 415429117
162 175800160
551 91178093
538 291536838
548 638623448
621 212673784
480 77193839
517 79168823
388 94692077
392 1000000000
184 101349634
543 521621165
644 1000000000
401 367060845
464 57422380
712 13336554
611 94863827
42 23171173
358 113168552
128 41476102
545 60072016
210 51437753
732 122946415
744 128795070
255 27378413
138 1000000000
370 755933141
383 571528665
540 99746955
720 540118999
422 205815597
581 136604721
632 194161274
134 1000000000
346 100732769
731 113191584
211 54760780
427 55216439
173 4684288
736 67774198
302 557460943
160 105606485
639 140420247
244 424236528
520 219942960
515 226400244
304 37526052
567 165365348
161 546764860
374 83243
129 201708708
777 231562279
249 773388772
504 82765507
209 199502390
683 233097641
401 201100001
618 38414152
576 881403328
412 704630
615 2563101
490 209513648
174 195291072
796 250494025
381 54437880
154 220603060
796 352792758
716 128870867
307 436949673
377 339914696
169 92272260
299 45247780
775 214427366
296 37764579
213 70230827
153 606334419
539 702645211
645 41096068
321 638951978
310 85156930
270 230434091
466 1000000000
43 103243038
642 212432678
672 355445878
174 533749054
405 20404016
670 61497558
146 118298933
410 252513605
191 104917831
9 61707694
515 1000000000
116 359664330
743 74958290
515 52397571
115 72533117
158 1000000000
79 29760685
397 343957746
2 42383721
727 1000000000
438 1000000000
6 32515951
81 253415125
448 20826904
252 1000000000
622 216238383
735 60226671
791 15268099
577 1000000000
197 304098373
300 188761304
414 5290307
166 79867858
363 113185958
216 30907576
84 280351147
458 350630530
449 125820357
260 129526649
314 2907315
525 51324070
102 1000000000
718 1000000000
142 355077321
431 196407326
218 18306458
56 89074919
274 45679868
145 15380212
606 480591571
194 15488591
5 93859858
786 1000000000
241 1000000000
554 1000000000
40 841987615
690 20029585
371 36544736
274 804363622
377 42824753
306 73545980
356 567049636
761 30361202
378 28158907
48 184746797
548 286091255
671 611386640
618 223809754
686 43583423
212 237422425
549 24415783
426 55049184
620 259413876
371 157833560
266 438059781
504 66942656
424 312630291
353 58166215
78 492735254
86 164597745
260 305680431
479 337934991
529 140291947
195 232339634
415 286344017
76 288865118
564 334443172
160 736334934
633 27388251
328 244664407
694 36385319
747 20688365
50 16464926
147 116410127
759 321323476
6 205567343
683 129037278
717 2378646
119 49457577
208 157979487
355 31701782
183 456153372
407 35834657
618 11819426
346 371344423
432 322327125
21 33107644
658 623748354
272 457589739
472 88640853
787 1100370
10 32396395
678 245319547
80 546054669
785 57719938
657 347765028
27 325049054
503 42722332
109 192790973
232 214790584
495 207863289
141 4118656
41 543520279
589 86843222
259 62613274
498 163973401
516 11402394
706 274677163
21 331885334
326 128529215
415 134933217
518 592910032
743 208794626
202 622269908
344 27961633
410 1000000000
505 249278784
317 70220022
465 63151842
668 862241127
265 34245003
671 458948345
265 37452364
654 145363447
441 42347014
593 149187475
224 225393139
495 82143752
680 269011548
178 32717199
535 517404030
160 2047866
502 52049669
2 182342481
45 136744878
319 88287352
483 260478399
705 432555140
706 420090600
270 365837423
464 64413961
752 41519314
214 1000000000
684 161925839
444 1000000000
749 828820432
10 316710970
186 7349054
231 252297151
218 1458445
220 179317020
662 237815010
530 234524363
535 71993307
302 144369575
354 36346287
571 1000000000
386 307541089
64 173681057
541 322571804
164 354054341
381 633078632
304 276167409
392 289887055
236 271467627
423 547917029
224 1000000000
193 123131532
116 22528652
96 1000000000
79 363761313
682 73907386
314 85496049
553 214574358
190 791187463
514 109217884
768 100520262
224 20623097
619 50146740
42 230337107
6 185682
391 1000000000
152 149621465
512 129672555
490 10430070
606 471183357
612 25179062
198 10890270
462 365564931
739 506082080
655 164741816
795 9931034
785 246154644
120 123310557
90 150074734
576 83440367
435 156226101
124 559689132
4 194403
371 424707340
52 23925696
719 296886556
237 28855040
246 154883256
213 1000000000
274 21843470
309 34709510
168 623490112
629 168904963
35 242352512
605 1000000000
234 69228156
372 334767616
196 218733819
3 121500309
58 5922713
563 272221892
85 1000000000
233 132565109
634 759791282
560 103845005
116 104251572
495 126799227
649 69619253
269 13528947
579 377782701
403 1000000000
456 202229608
137 77992600
353 474130317
695 136581608
309 3098519
5 137470605
46 137008463
250 175584351
146 312144270
703 63941989
203 488341026
61 98622467
734 134717921
217 324254506
182 248017217
414 1000000000
602 849548285
51 587269330
465 13573666
543 1000000000
4 362612553
555 16030925
508 702226035
671 9842043
478 16772798
67 138677685
405 187952148
254 121609921
776 19955353
730 170847286
318 72675575
477 5978433
768 78691967
624 224100902
438 1000000000
507 175037668
232 554480059
165 78842767
541 630310640
344 1000000000
318 93581722
442 126440563
148 638761733
148 95611617
389 713489930
494 6573280
633 49943146
48 31578416
666 156260296
737 308303774
78 257842366
650 295880245
575 35081937
564 1000000000
595 321670509
228 152545760
18 108446212
293 1000000000
774 572063952
30 1000000000
278 246731201
374 1000000000
41 165606423
150 81583340
104 142078396
454 1000000000
475 98121352
78 264670842
266 545918218
182 1333918
348 565649636
325 18833859
26 16376420
260 17104102
461 62875470
700 240768421
443 49656545
242 168212407
44 1000000000
305 1000000000
490 433816170
480 110386562
123 230924650
678 894570613
73 1000000000
236 202924808
538 195155598
218 182715476
598 1000000000
632 100889319
391 409594872
429 247711121
180 25492788
195 146064047
644 23030343
672 2012774
320 266796950
621 221114801
656 41231389
530 1000000000
412 203448433
790 108535854
331 1000000000
291 11302385
230 971609087
767 41947724
662 84370800
787 3662764
641 90325285
679 1000000000
15 438294611
771 28499058
586 35432194
270 69422416
376 169611160
561 6853950
579 1000000000
213 946995660
593 27014300
31 492658920
138 1000000000
570 125140328
56 1000000000
525 33381972
290 242323125
383 706603521
335 103334043
505 347923295
40 91693200
643 28286584
437 648982604
165 91751909
606 86720028
647 13099255
74 144180338
48 14429231
482 223931752
106 1000000000
271 181559494
187 244835311
407 135016061
235 20132677
66 102611811
772 306659541
634 118378040
205 13048757
197 388880763
109 1000000000
13 1461050
429 867799163
312 329421362
757 26993760
142 72929001
397 140214236
121 188164407
700 14608646
544 333239841
556 101235300
554 298273116
579 315170418
192 409908839
202 17040084
490 405472551
425 198261461
688 429574902
391 243129666
473 162692842
302 730574750